《《数据结构与算法》期末练习题.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》期末练习题.docx（40页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法期末练习题数据结构与算法期末练习一选择题1以下与数据的存储结构无关的术语是（ D ）。A循环队列 B. 链表 C. 哈希表 D. 栈2. 算法的时间复杂度取决于（ A ）A问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu3. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 24. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数
2、的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ）A（1），（2） B（1） C（1），（2）,(3) D.（2）5对于有n 个结点的二叉树, 其高度为（ D ）Anlog2n Blog2n C?log2n?|+1 D不确定6从下列有关树的叙述中,选出正确的叙述（ C ）A二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B当K1时高度为K的二叉树至多有2k-1个结点。C哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。D在二叉树中插入结点,该二叉树便不再是二叉树。7设无向图的顶点个
3、数为n，则该图最多有（ B ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En28已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V79下列排序算法中，其中（ D ）是稳定的。A. 堆排序，冒泡排序B. 快速排序，堆排序C. 希尔排序，归并排序D. 归并排序，冒泡排序10对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25
4、 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 (4） 15 21 25 47 8411. 则采用的排序是 ( A )。A. 选择B. 冒泡C. 快速D. 插入12以下数据结构中，哪一个是线性结构（ D ）？A广义表 B. 二叉树 C. 稀疏矩阵 D. 串13下面关于线性表的叙述中，错误的是哪一个？（ B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。14. 设一个栈的输入序列是 1，2，3，4，5,则下列序列
5、中，是栈的合法输出序列的是（ D ）。A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 1 2 5D. 3 2 1 5 415. 设n为正整数.下列程序段中前置以的语句的频度为（ B ）。i = 1; k = 0;do k+= 10*i;i+;While(i A. n 1B. nC. n + 1D. n - 216. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）A?logn?+1 Blogn+1 C?logn? Dlogn-117一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1A. 不确定B. n-i+1C. iD. n-i18n个结点的完全有向图
6、含有边的数目（ D ）。An*n n（n） Cn2 Dn*（nl）19稳定的排序方法是（ B ）A直接插入排序和快速排序 B折半插入排序和起泡排序C希尔排序和四路归并排序 D树形选择排序和shell排序20有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。A下面的B，C，D都不对。 B9，7，8，4，-1，7，15，20C20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，2021以下那一个术语与数据的存储结构无关？（ A ）A栈 B. 哈希表 C. 线索树 D. 双向链表22下面关于串的的叙述中，
7、哪一个是不正确的？（ B ）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储23. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。A. a，c，b，dB. b, c，d，aC. c, d，b, aD. d, c，a，b24.关于二叉树的叙述：只有一个结点的二叉树的度为0; 二叉树的度为2；二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是（ D ）A B C D25高度为 K的二叉树最大的结点数为（ C ）。A2k B2k-1 C2k
8、-1 D2k-1-126从下列有关树的叙述中,选出正确的叙述（ C ）A二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B当K1时高度为K的二叉树至多有2k-1个结点。C用树的前序遍历和中序遍历可以导出树的后序遍历。D哈夫曼树是带权路径最长的树,路径上权值较大的结点离根较近。27. 关键路径是事件结点网络中（ A ）。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路28用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。A逆拓扑有序 B拓扑有序 C无序的29一组记录的关键码为（46，79，56，38，4
9、0，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。A(38,40,46,56,79,84) B. (40,38,46,79,56,84)C(40,38,46,56,79,84) D. (40,38,46,84,56,79)30. 一个向量的第一个元素的地址是begin，每个元素的长度是k ，则第i个元素的地址是( D )A. begin+(k-1)iB. begin+(k-2)iC. begin+kiD. begin+(i-1)k31. 有一个有序表为 1，3，9，12，32，41，45，62，77，88，92，100，用折半查找法，若要找63，要经过( C
10、)次与63比较。A. 12B. 6C. 4D. 532. 一个序列的初始状态为（46，77，82，53，31，70），今对其进行冒泡排序，当进行两趟冒泡后，序列中的元素排列为( D )。A.（31，46，70，53，77，82）B.（46，77，53，31，70，82）C.（46，31, 82，53，77，70）D. (46 ，53，31，70，77，82)33. 将一个长度为n的向量的第i 个元素删除时，需要前移( B )个元素。A. iB. n-iC. n+1D. n-i+134. 不带表头的单链表，头指针为head ，判断其是否为空的条件是( A )A. head=0B. head-ne
11、xt=nullC. head=headD. head-next=head35. 在一个单链表中，已知*q是（*q表示指针q所指的结点，以下同）*p的前驱结点，在*q之后插入结点*s，正确的操作步骤序列是( A )。A) q-next=s; s-next =p B) s-next=p-next; q-next=s;C) p-nexr=s; s-next=p ; D) p-next=s; s-next=q;36. 非空循环链表head 的尾结点 *p 满足下列( C )条件A) head-next=p; B) head=p; C) p-next=head; D) p-next=037. 一个栈的输
12、入序列是a,b,c,d,e ，则可能的出栈序列是( D )。A. ecdab B) cebda C) daecb D) abcde38. 设栈s的类型为sqstack ，判定栈空的条件是( C )。A. s=NULL B) s-top=0 C) s.top=0 D) s.top=NULL39. 深度为5 的二叉树至多有个( B )结点。A. 12B. 31C. 14D. 1540. 已知二叉树的后、中根序列分别是bedfca 和 badecf，则该二叉树的前根遍历序列是( C )。A) defbca B) fedbca C) abcdef D) fedcba41. 一个有n个顶点的有向图最多有
13、( B )弧。A) n(n+1) B) n(n-1) C) n(n+1)/2 D) n(n-1)/242. 具有n个顶点的无向图至少要有( B )条边才有可能是一个连通图。A) n(n+1) B) n-1 C) n+1 D) n(n-1)43. 已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( B )。A) 1 2 3 4 B) 1 4 2 3 C) 1 3 2 4 D) 1 4 3 2 44. 一个向量的第一个元素的地址是100，每个元素的长度是 2 ，则第五个元素的地址是( C )A) 102 B) 110 C) 108 D) 12045. 一个循环顺序队列 ,队
14、头、尾指针的值分别为front,rear ，则队列中元素个数为( A )。（maxlen 为循环顺序表的长度） A. (rear-front+maxlen) % maxlen B. (rear-front) % maxlen C. rear-front+1 D. front-rear+146. 一个有n 个顶点的图最少有( D )条边。A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 047. 具有5个顶点的无向图至少要有( A )条边才能确保是一个连通图。 A) 4 B) 5 C) 6 D) 748. 设栈s 的类型为sqstack ，最多可容纳maxlen 个元素，则判
15、定栈满的条件是( B )。 A. s=maxlen-1 B) s.top=maxlen-1 C) s-top=maxlen-1 D) s.top=049. 一个顺序队列q 的类型为sqqueue,队头、尾指针分别为front,rear ，最多可容纳maxlen 个元素，则队空的条件是( C )。A) front=rear B) rear=0 C) q.front=q.rear D) rear=maxlen-150. 在具有n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( B )A.O(1)B.O(n)C.O(nlogn)D.O(n*n)51. 链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更
