《数据结构考试题》由会员分享,可在线阅读,更多相关《数据结构考试题(53页珍藏版)》请在金锄头文库上搜索。
1、一、单项选择1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的c、数据信息在计算机中的a以及一组相关的运算等的课程。 A.操作对象B.计算方法C.逻辑结构D.数据映象 A.存储结构B .关系C .运算D.算法2. 以下数据结构中,D 是线性结构。A.广义表B.二叉树C.稀疏矩阵D.串3. 从逻辑上可以把数据结构分为 C 两大类。A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构 D.初等结构和构造型结构4. 以下数据结构中,D 是线性结构。5.6.7.A.8.A.广义表B.二叉树 C.稀疏矩阵D.串以下数据结构中,D 是非线性结构。A 栈B.二叉树 C.队列D.字
2、符串数据结构DS(Data Struct)可以被形式地定义为DS=(D, R),其中D是B的有限集合,A.算法A.操作B.数据元素B.映象线性表的顺序存储结构是一种随机存取C.C.数据操作存储的存储结构,D.数据对象D.关系线性表的链式存储结构是一种的B.顺序存取 C-索引存取 D.散列存取线性表的逻辑顺序与存储顺序总是一致的,这种说法_B_。R是D上的D有限集合。B 存储结构。A.正确B.不正确9. 下面那一条是顺序存储结构的优点? (A)A .存储密度大 B.插入运算方便C.删除运算方便D.可以方便的用于各种逻辑结构的存储表示10. 线性表采用链式存储结构时,要求内存中可用的存储单元的地址
3、 .A .必须是连续的 B.部分地址必须是连续的 C. 一定不连续D.连续和不连续都可以11. 表长为n的顺序存储的线性表,当在任何位置上插入和删除一个元素的概率相等时,插入一个元素所需要移动元素的平均次数为E ,删除一个元素所需要移动元素的平均次数为AA.(n-1)/2B.n C. n+1 D. n-1 E. n/2 F. (n+1)/2 G. (n-2)/212. 带头结点的单链表head为空的判定条件是_B。A. head=NULLB. head-next= =NULLC. head-next= =headD. head!=NULL13. 在一个单链表中,若删除p所指向结点的后继结点,则
4、执行_A。A.p-next= p-next-next B. p=p-next; p-next= p-next-nextC. p= p-next-nextD. p= p-next14. 若已知一个栈的入栈序列是1,2,3,n,其输出序列为p1,p2, p3,pn,若p1=n,则pi为 CA. iB. n=i C. n-i+1 D.不确定15. 设栈的输入次序为:1 , 2, 3, 4, 5,则不可能是其出栈序列.A. 54321 B. 45321C. 43512D.1234516. 一个递归算法必须包括 BA. 递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分17. 用方式存储的
5、队列,在进行删除操作时DA仅修改头指针B.仅修改尾指针C.头尾指针都要修改D.头尾指针可能都要修改18. 数组Am存放循环队列的元素,其头尾指针分别是front和rear,则当前队列的元素个数是_A.A. (rear-front+m)%mB. (front-rear+m)%mC. front-rear+1 D. rear-front+119.栈和队列的共同特点_C_。A.都是先进先出B.都是先进后出C.允许在端点插入和删除元素D.没有共同点20. 一个栈的入栈序列a,b,c,d,e,则栈的输出序列是_A。A. edcba B. decba C. dceab D. abcde21. 栈的特点是_
6、B_,队列的特点是_A_。A.先进先出 B.先进后出22. 从一个栈顶指针HS的链表中删除一个结点,用x保存被删除的结点值,执行的语句为_CA. x=HS; HS=HS-nextB. HS=HS-next; x=HS-dataC. x=HS-data; HS=HS-nextD. HS-next=HS; x=HS-data23. 在链队列Q中,插入s所指向的结点执行的语句为_C_。A. Q.front-next=s; B. Q.rear-next=s; Q.rear=sC. s-next=Q.rear;Q.rear=s D. s-next=Q.front;Q.front=s24. 空串与空格串是
7、相同的,这种说法_B_。A.正确B.不正确25. 下面关于串的叙述,哪一个是不正确的_B_。A.串是字符的有限序列B.空串是由空格构成的串C.匹配模式是串的一种重要运算 D.串可以采用链式存储结构26. 设有两个串p和q,求q在p中首次出现的位置的运算称作B.word.A.连接B. 模式匹配C.求子串D.求串长27. 若串s二software,其子串的数目为BA. 8 B. 37 C. 36 D. 928. 二维数组A中,每个元素A的长度为3个字节,行下标i从0到7数组按行存放时,数组元素A7 4的起始地址为_C_。A. SA+141 B. SA+144 C. SA+222 D. SA+225
8、29. 对稀疏矩阵进行压缩存储的目的是_C_.A.便于进行矩阵运算B.便于输入输出C节省存储空间D.降低运算的时间复杂度,列下标j从0到9,从首地址SA开始连续存放在存储器内,该.word.30. 在以下叙述中正确的是 BA. 线性表的线性存储结构优于链表存储结构B. 二维数组可以看成是其数据元素为线性表的线性表C. 栈的操作方式是先进先出D. 队列的操作方式是先进后出31. 广义表(a),a)的表头为C ,表尾为 C .A. ()B. a C. (a) D. (a)D_。32. 已知广义表L=(x,y,z),a,(u,t,w),从L中取出原子项t的运算为A. Head(Tail(Tail(L
9、)B. Tail(Head(Head(Tail(L)C. Head(Tail(Head(Tail(L) D. Head(Tail(Head(Tail(Tail(L)33. 树最适合用来表示 BA.有序的数据元素B.数据之间具有分支层次关系的数据C.无序的数据元素D.无太多关系的数据元素34. 如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为_B_。A. uwvtsB. vwutsC. wuvts D. wutsv35. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是D.A. bdgc
10、efha B. gdbecfha C. bdgaechf D. gdbehfca36. 在一非空二叉树的中序遍历序列中,根结点的右边_A_。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D. 只有左子树上的所有结点37. 设m和n是一棵二叉树上的两个结点,在中序遍历,n在m前的条件是CA. n在m的右方 B. n是m的祖先C. n在m的左方 D. n是m的子孙38. 深度为5的二叉树至多有_C_个结点。A. 16B. 32C. 31D. 1039. 由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为 A. 23B. 37C. 46D. 4
11、340. 利用二叉链表存储树,则根结点的右指针是 CA.指向最左孩子B.指向最右孩子C.空D.非空41. 下列存储方式中,哪一个不是树的存储形式? DA.双亲表示法B.孩子链表表示法C.孩子兄弟表示法 D.顺序存储表示法42. 在一个无向图中,所有顶点的度数之和等于所有边数的_C_倍。A. 1/2B. 1 C. 2 D. 443. 具有n个顶点和多于n-1条边的无向图 B .A.有可能是树B.-定不是树C.-定是树D.以上答案都不对44. 具有6个顶点的无向图至少应有_A_条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 845. 无向图 G=(V,E),其中:V=a,b,c,d,
12、e,f, E=(a,b),(a,e),(a,c), (b,e),(c,f),(f,d),(e,d),则对该图进行深度优先遍历,得到的序列为:DA. abecdf B. acfebd C. aebcfd D. aedfcb46. 下述几种排序方法中,要求内存量最大的是_DoA.插入排序B.选择排序C.快速排序D.归并排序47. 排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上 的方法,称为_C_。A.希尔排序 B.起泡排序 C.插入排序D.选择排序48. 在待排序的元素序列基本有序的前提下,效率最高的排序方法是_A_。A.插入排序
13、B.选择排序C.快速排序 D.归并排序49. 下列排序算法中,哪一个是稳定的排序算法?BA.直接选择排序B.二分法插入排序 C.希尔排序 D.快速排序50. 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数 AA. nB. 2n-1C. 2nD. n-1二、填空题1. 算法的五个重要特性是 有穷性,确定性,可行性,输入和输出.2. 数据的树型结构和图(网)状结构合称非线性结构.3. 抽象数据类型的定义仅取决于它的一组 逻辑特性,而与 数据在计算机中的表示和实现 无关.4. 评价算法质量的指标是 正确性,易读性,健壮性,高效性.5. 数据结构中评价算法的两个重要指标是:时间复杂度和空
14、间复杂度.6. 分析下面算法(程序段),的时间复杂度是O (mn) 。s=0;for (i=0;in;i+)for (j=0;jm;j + +)s+=Bij;7. 当线性表元素的总数基本稳定,且很少进行删除和插入操作时,但是要求以最快的速度存取线性表中的元素,应该采取 顺序 存 储结构.8. 顺序表中逻辑上才目邻的元素的物理位置必定才目邻,而单链表中逻辑上才目邻的元素的物理位置不一定才目邻.9. 在各个结点查找概率相等的情况下,从n个结点的单链表中查找一个结点,平均要访问n/2 个结点.10. 在单链表中设置头指针的作用是:简化操作,减少边界条件的判断.11. 在单链表中,除首元结点外,任一结点的存储位置由 其直接前驱的指针域指示.12. 对于一个具有n个结点的单链表,在已知p所指向结点后插入一个新结点的时间复杂度是 O,在值域为给定值的结点后插入 一个新结点的时间复杂度为O(n).13. 在双链表中,每个结点有两个指针域,一个指向前驱结点,另一个指向后继结点。14. 根据线性表的链式存储结构中每一