(149) 算法的 健壮特性是指做为一个好的算法，当输入的数据非法时，也能适当地做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。
(150) 算法分析不是针对实际执行时间的精确的算出算法执行具体时间的分析，而是针对算法中语句的 执行次数做出估计，从中得到算法执行时间的信息。
(151) T(n)=O(f(n))，它表示随问题规模n的增大算法的执行时间的增长率和f(n)的增长率 相同，称作算法的渐进时间复杂度，简称时间复杂度。
(152) 若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为 原地工作，辅助空间为O(1)。
(153) 在带有头结点的单链表中L中，第一个元素结点的指针是 。L->next
(154) 在一个带头节点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= 。p->next->next
(155) 设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句: py->next=px->next; px->next=py。 (156) 对于栈操作数据的原则是 。后进先出 (157) 设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为 。(rear-front+m)%m
(158) 若已知一个栈的入栈序列是1,2,3,4??n，其输出序列为
p1,p2,p3,??pn，若p1= =n,则pi为 。n-i+1 (159) 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
(160) 通常程序在调用另一个程序时，都需要使用一个 栈来保存被调用程序内分配的局部变量。形式参数的存储空间以及返回地址。 (161) 栈下溢是指在___栈空_____时进行出栈操作。 (162) 用P表示入栈操作，D表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的P和D的操作串为_______ 。PDPPDPDD
(163) 在具有n个单元的循环队列中，队满共有 n-1个元素。
(164) 队列是被限定为只能在表的一端进行插入运算，在
表的另一端进行删除运算的线性表。
(165) 循环队列的引入，目的是为了克服_______假溢出。
(166) 所谓稀疏矩阵指的是_______非零元很少(t< (167) 在稀疏矩阵表示所对应的三元组线性表中，每个三元组元素按 行为主序， 列号为辅序的次序排列。 (168) 二位数组Am×n按行优先顺序存储在内存中，元素a00地址为loc(a00),每个元素在内存中占d个字节，元素aij的地址计算公式为loc(aij)= loc(a00)＋(i*n+j)*d 。 (169) 去除广义表LS=(a1,a2,a3,??，an)中第1个元素，由其余元素构成的广义表称为LS的____表尾_____。 (170) 树内个结点的度 最大值称为树的度。 (171) 一个二叉树第5层节点最多有 16个。 (172) 已知完全二叉树T的第5层只有7个结点，则该树共有____11____个叶子结点。 (173) 在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______N2+1。 (174) 假设用于通信的电文由8个字母组成，其频率分别为 7,19,2,6,32,3,27,10。设计哈夫曼编码，其中字母的编码长度最大是 5位。 (175) 一棵具有257个结点的完全二叉树，它的深度为 。 9 (176) 图的深度优先遍历序列 不是 惟一的。 (177) 在图中，任何两个结点之间都可能存在关系，因此图的数据元素之间时一种 多对多 的关系。 (178) 在有向图中，以顶点v为终点的边的数目称为v的___入度_____。 (179) 一个无向图有n个顶点，e条边，则所以顶点的度数之和为 2e。 (180) 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。 (181) (182) 有向图G用邻接表矩阵存储，其第i行的所有非零元素之和等于顶点i的 。出度 (183) 如果n个顶点的图是一个环，则它有 棵生成树。 n （以任意一顶点为起点，得到n-1条边） (184) n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 。O(n2) (185) n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 。O(n+e) (186) 设有一稀疏图G，则G采用 邻接表 存储较省空间。 (187) 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。 (188) 图的逆邻接表存储结构只适用于 有向 图。 (189) 已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0 。 (190) 图的深度优先遍历序列 不是 惟一的。 (191) n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储时，该算法的时间复杂度为 O(n+e) 。 (192) n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时 间复杂度为 O(n2)；若采用邻接表存储，该算法的时间复杂度为 O(n+e) 。 (193) 图的BFS生成树的树高比DFS生成树的树高 小或相等 。 (194) 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的 时间复杂度为 O(n2)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。 (195) 若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔(Kruskal) 算法来求解。 (196) 若要求一个稠密图G的最小生成树，最好用 普里姆(Prim) 算法来求解。 (197) 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。 (198) 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。 (199) 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。 (200) 散列法存储的基本思想是由 关键字的值决定数据的存储地址。 (201) 大多数排序算法都有两个基本的操 作： 。比较和移动 (202) 由于查找算法的基本运算是关键字之间的比较操作，所以可用 平均查找长度来衡量查找算法的性能。 (203) 查找有静态查找和动态查找，当查找不成功时动态查找会 将查找关键字插入在表中。 (204) 顺序查找法中设置监视哨，可以起到 防止越界的作用。 (205) 假设列表长度为n，那么查找第i个数据元素时需进行 n-i+1次比较。 (206) 假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为： ASL=(n+1)/2。 (207) 折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是 按关键字大小有序排列的顺序表。 (208) 假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等， (209) 在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为 2。 (210) 折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。 (211) 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找。 (212) 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 (213) 当关键字集合很大时，关键字值不同的元素可能会映象到哈希表 的同一地址上，即 k1≠k2 ，但 H（k1）=H（k2），这种现象称为 冲突. (214) 产生冲突现象的两个关键字称为该散列函数的 ____同义词________ 。 (215) 在散列函数 H(key)=key MOD p 中，p应取 素数。 (216) 设哈希表长m=14, 哈希函数H(key)=key MOD11.表中已有4个结点；addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7, 其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是 。9 (217) 希尔排序是属于 插入排序的改进方法。 (218) 给出一组关键字T＝（20,4,34,5,16,33,18,29,2,40,7），要求从下到大进行排序，试给出快速排序（选一个记录为枢纽）第一趟排序结果 。7,4,2,85,16,18,20,,29,33,40,34 (219) 大多数排序算法都有两个基本的操作： 比较和移动 。 (220) 在对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排 序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 次。6。 (221) 在插入和选择排序中，若初始数据基本正序，则选用 插入 ；若初始数据基本反序，则选用 选择 。 (222) 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。 (223) 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速排序，在最坏的情况下所需要的时间是 O(n2) (234) 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所需要的附加空间是 O(n) 。 7． 对于n个记录的表进行2路归并排序，整个归并排序需进行 ┌log2n ┐ 趟（遍）。 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构试题库答案 nana(5)在线全文阅读。
相关推荐：