(C) 3，2，5，6，8 (D) 2，3，6，5，8
（ B ）27. 判定一个栈ST（最多元素为m0）为空的条件是
Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0
Ｄ．ST->top=m0
（ C ）28. 在一个图中，所有顶点的度数之和等于图的边数的 倍。
A．1/2 B. 1 C. 2 D. 4
（ B ）29. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
A．1/2 B. 1 C. 2 D. 4
（ B ）30. 有8个结点的无向图最多有 条边。 A．14 B. 28 C. 56 D. 112
（ B ）31.设有三对角阵A[1..100，1..100]，若将其非零元素按行优先的顺序存入一维数组B[1..298]中，则A中元素A66,65（即该元素下标i=66，j=65）保存在B中下标为（ ）的位置上。
A．198 B．195 C．197 D．196
（ B ）32.在一棵度为4的树T中，若有1个度为4的结点，1个度为3的结点，2个度为2的结点，4个度为1个的结点，则数T的叶子结点个数是（ ）。
A．5 B．8 C．6 D．7
（ A ）33.深度为h的满m叉树的第k层有（ ）个结点。(1= A．mk-1 B．mk-1 C．mh-1 D．mh-1 （ D ）34.n个结点的有向完全图含有边的数目（ ）。 A．n*n B．n*(n+1) C．n／2 D．n*(n-1) （ B ）35.下列方法中可以判断出一个有向图是否有环（回路）的是（ ）。 A．广度优先遍历 B．深度优先遍历 C．求最短路径 D．求关键路径 （ D ）36.下面关于二分查找的叙述正确的是（ ）。 A．表必须有序，表可以顺序方式存储，也可以链表方式存储 B．表必须有序且表中数据必须是整型，实型或字符型 C．表必须有序，而且只能从小到大排列 D．表必须有序，且表只能以顺序方式存储 （ C ）37. 有8个结点的有向完全图有 条边。 A．14 B. 28 C. 56 D. 112 （ B ）38．在表长为ｎ的链表中进行线性查找，它的平均查找长度为 Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２; Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１ （ A ）39．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。 若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。 A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 （ C ）40．对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。 A．3 B．4 C．5 D． 6 （ A ）41. 链表适用于 查找 A．顺序 B．二分法 C．顺序，也能二分法 D．随机 （ B ）42.下面关于m阶B树说法正确的是（ ）。 ①每个结点至少有两棵非空子树 ②树中每个结点至多有m-1个关键字 ③所有叶子在同一层上 ④当插入一个数据项引起B树结点分裂后，树长高一层 A．①②③ B．②③ C．②③④ D．③ （ D ）43.下列排序算法中，（ ）是不稳定的。 A．堆排序，冒泡排序 B．快速排序，堆排序 C．直接选择排序，归并排序 D．堆排序，希尔排序 （ A ）44.设一组初始记录关键字序列为(345,253,674,924,627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。 A．3 B．4 C．5 D．8 （ C ）45.用一维数组存放的一棵平衡二叉树如下图所示， 24 13 53 0 0 37 90 插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点保存的关键字分别是（ ）。 A．13,48 B．24,48 C．24,53 D．24,90 （ D ）46.二叉树的第k层的结点数最多为( ). A．2-1 B.2K+1 C.2K-1 D. 2 （ D ）47.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 （ C ）48. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） k k-1 （ D ）49.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A．1 B．2 C．3 D．4 （ A ）50.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 （ D ）51．算法指的是（ ） A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 （ B ）52．线性表采用链式存储时，结点的存储地址（ ） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 （ C ）53．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ） A．O（1） B．O（n） C．O（m） D．O（m+n） （ B ）54. 设有以下四种排序方法，则（ ）的空间复杂度最大。 (A) 冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希尔排序 （ D ）55．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ） A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m （ A ）56．如下陈述中正确的是（ ） A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串 （ C ）57．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算 n法时，在最坏情况下的时间复杂度是（ ） A．O（3） B．O（n） C．O（n2） D．O（n3） （ D ）58．一个非空广义表的表头（ ） A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子 （ A ）59．假设以带行表的三元组表表示稀疏矩阵，则和下列行表 0 2 3 3 5 对应的稀疏矩阵是（ ） ?0?8?70??0?8000A.?0?0052C.???00??50 ?? ?000000040046??0??0?706????0??0B.0??5???070D.?0???005??0? ????00??0? ?8?8000003006?6?000???400?0??000?0??040??0 ?300?? （ C ）60．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数 为1,则度为0的结点个数为( ) A．4 B．5 C．6 D．7 （ D ）61．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A．e B．2e C．n2－e D．n2－2e （ C ）62．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与 某个顶点vi相关的所有弧的时间复杂度是( ) A．O(n) B．O(e) C．O(n+e) D．O(n*e) （ D ）63．用某种排序方法对关键字序列（25，84，21，47，15，27，68， 35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ） A．选择排序 B．希尔排序 C．归并排序 D．快速排序 （ C ）64．适于对动态查找表进行高效率查找的组织结构是（ ） A．有序表 B．分块有序表 C．三叉排序树 D．线性链表 （ B ）65．不定长文件是指（ ） A．文件的长度不固定 B．记录的长度不固定 C．字段的长度不固定 D．关键字项的长度不固定 （ C ）66.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。 A n B n/2 C (n+1)/2 D (n-1)/2 （ D ）67.在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。 A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; （ A ）68. 栈的插入和删除操作在（ ）进行。 A 栈顶 B 栈底 C 任意位置 D 指定位置 （ B ）69.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） A 24 B 71 C 48 D 53 （ B ）70．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫 曼树中总共有（ ）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m
