数据结构习题

1、数据结构习题算法指的是(计算机程序 排序算法从逻辑上可以把数据结构分为(A. 动态结构、静态结构C. 线性结构、非线性结构3. 算法分析的两个主要方面是A. 空间复杂性和时间复杂性 C. 可读性和文档性4. 程序段如下：1AC2.)。)B.D.sum=0 ；for(i=1;i<=n;i+)for(j=1;j<=n;j+)B. 解决问题的计算方法D. 解决问题的有限运算序列。 )两大类。B. 顺序结构、链式结构D. 初等结构、构造型结构正确性和简明性 数据复杂性和程序复杂性sum+ ；n 为正整数，则其时间复杂度为( A. O(n )B. O(nlogn)5. 下列属于非线性结构的是

2、( )。(多选) A. 数组 B. 图 C. 6. 若长度为 n 的线性表采用顺序存储结构， 算法的时间复杂度为()(1<=i<=n+1)AO(0)BO(1)7. 下面程序段的时间复杂度是 ( for(i=0;i<n;i+)for(j=1;j<m;j+)Aij=0 ； A.O(n) B.O(m+n+1) 8. 下面程序段的时间复杂度是 (for ( a=0 ; a < x ; a + ) b=0 ;while ( b < y ) Sab =a * y ; b+;A. O(a*b) B. O( a ) 9. 数据结构被形式地定义为 (K,R ) 上的( )有限

3、集合。 A. 操作 B. 映像 10. 设树 T 的度为 4，其中度为 1， 则 T 中的叶子数为( )。A5B 6)。)。C. O(n 3)D. O(n 2)队列 D. 线性表 E. 树 在其第 i 个位置插入一个新元素的CO(n)DO(n2)C.O(m+n) )。D.O(m*n)C., 其中D. O( x )O( x*y)K 是数据元素的有限集合， R 是 KC. 存储 D. 关系 2，3 和 4 的结点个数分别为 4 ，2，1 ，1，C7D8一个队列的入队序列是 A, B, C, D，则队列的输出序列是（D,C,B,AB. A,B,C,DA,D,C,BD. C,B,D,A在一个无表头结点

4、的单链表 HL 中，若要向表头插入一个由指针 则执行 （）。HL=p; p->next=HL; p-next=HL; HL=p; p->next=HL; p=HL; p->next=HL->next; HL->next=p;在一个单链表中 ,若 q 所指结点是 p 所指结点的直接前驱结点）。11.A.C.p 指向的结12. 点，A.B.C.D., 若在 q 与 p13. 之间插入一个 s 所指的结点 ,则执行 （s->next=p->next; p->next =s; p->next =s->next; q->next =s;

5、在单链表中，p->next =s; s->next =q;s->next=p; s->next =p;指针 p 指向元素为 x 的结点，实现“删除 x 的直接后继结点” ）。A.B.C.D.14. 的语句是 （B. p->next=p->next->next;D. p=p->next->next;A. p=p->next;C. p->next=p;B head->next=NULL; Dy 的值分别等于（15. 对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是 （）。 （ 不带表头结点的单链表呢 ?）

6、head!=NULL;）。Ahead=NULL; Chead->next= =head;初始化栈 进栈 出栈 和 20/16. 运行以下代码段后， int x=10,y=20; InitStack（S）; Push（S,x）; Push（S,y）; Pop（S,x）; Pop（S,y）;C. 10 和 10 ）。D. 20和 20A. 20 和 10 B. 1017. 以下叙述中正确的是（C. 18.A.19.B. 串的长度必须大于零D. 空串就是空白串）进行。C. 任意位置）。B. 终止条件和递归部分D. 终止条件和迭代部分右括号是否配对出现的算法，D.指定位置A. 串是一种特殊的线性

7、表 串中元素只能是字母 栈的插入和删除操作在（ 栈顶 B. 栈底 一个递归算法必须包括（A. 递归部分C. 迭代部分采用（）数据20. 设计一个判别表达式中左， 结构最佳。B. 队列D. 栈A .线性表的顺序存储结构C. 线性表的链式存储结构21. 栈在（）中应用。C. 表达式求值）。D. A,B,C 都对A. 递归调用B. 子程序调用22. 对稀疏矩阵进行压缩存储主要目的是（A .便于进行矩阵运算 C.节省存储空间 23.设有三个元素 出栈排列是（A. XYZB .便于输入和输出D 降低运算的时间复杂度X，Y，Z顺序进栈（进栈过程中允许出栈），下列得不到的）。B. YZXC. ZXYD. Z

8、YX24. 有一个二维数组A1:6 ,1:8，每个数组元素用相邻的6个字节存储，存 储器按字节编址，已知 A的基地址是0。若按行存储，则A2，4的首地址是（）。（按列存储呢？）A.200B. 120C. 6625. 最大容量为n的循环队列，队尾指针是I的条件是（）。（队满呢？）A. （rear+1） % n=frontC. rear+1=front26. 树最适合用来表示（）A.有序数据元素C.元素之间具有分支层次关系的数据27. 深度为6 （根的层次为1 ）的二叉树至多有（A.28. 设一棵二叉树的先序遍历和中序遍历所得序列分别是 该树的后序遍历序列为（A. abcdB. dbcaC. cd

9、ba29. 在一个图中，所有顶点的度数之和等于所有边数的（A.30. 设有一 AOV-网如右图所示， AOV-网的拓扑序列是（D. 114rear，队头指针是front，则队空B. rear=fro ntD. (rear-1) % n=frontB.D.641/2B. 32C. 31无序数据元素 元素之间无联系的数据）结点。D.abdc63和bdac ，则D.B. 1C. 2该B.D.13245不能进行拓扑排序A. 12345C. 5423131. 一棵含18个结点的二叉树的高度至少为（A. 3B. 4C. 532. 无向图中一个顶点的度是指图中 A.通过该顶点的简单路径数 C.通过该顶点的回

10、路数33. 有一个二维数组A1:6，0:7 储器按字节编址，假设存储数组元素dbac)倍。)。5存储，贝U A2，4的第一个字节的地址是（A. 72B. 96关键路径是事件结点网络中从源点到汇点的最长路径最长回路34.A.C.35.D. 6（ ）。B.与该顶点相邻接的顶点数D.与该顶点连通的顶点数，每个数组元素用相邻的6个字节存储，存A1，0的第一个字节的地址是0。若按行 ）。一组记录的排序码为（46，79，56序）的方法建立的初始堆为（A. 79，46，56，28，40，100C. 100，79，56，28，40，46C. 120）。B 从源点到汇点的最短路径D.最短回路，28，40，100

11、），贝闲用堆排序（升 降序？）B. 28，46，56，79，40，100D. 100 ，56，79，40，46，28D. 23436. 设某广义表 H=(A，( a,b,c,d )，则表达式 tail(head(tail(H) head(head(tail(H) 的值是( )；求原子 b 的表达式是(A. F.37. A38.的值是( )；)D. (b,c,d) E. d G. tail(tail(head(tail(H)B. 8 、4、6 、5D. 8 、4 、7、546 ，27 ，56 ，38 ，40 ，9，39 )，使用间隔 d1=2 ， 记录的排序码顺序为( )B. 39, 9, 40

12、, 27, 46, 38, 56D. 9, 27, 38, 39, 40, 46, 56)算法可能会出现当初始数据有序时，话费的时间C. 求子串 ( )B. 索引文件 D. 间接存取文件 错误的是( 必须占用一片连续的存储单元。 便于进行插入和删除操作。 不必占用一片连续的存储单元。 便于插入和删除操作。46.ABCD47.)。A B. a C. c head(tail(head(tail(H) 设无向图的顶点个数为n,则该图最多有()条边。(有向图？)n-1Bn(n-1)/2C n(n+1)/2D n(n-1)当初始序列已经按键值有序,用直接插入算法对其进行排序,总的比较次 数为 ( )次，

13、移动记录的次数达到最小值 2(n-1) 次。A. 1B. nC. n-1 D. n(n-1)/239. 在已知待排序文件已基本有序的前提下，效率最高的排序方法是 ( ) A. 直接插入排序B. 简单选择排序C. 快速排序D. 归并排序40. 对有 15 个元素的有序表作二分 ( 折半) 查找,则查找 A5 的比较序列 的下标为 ().A. 8 、4 、5 C. 9 、4 、5 41. 一组记录的排序码为( 做一趟希尔排序(升序)后， A. 46, 27, 56, 38, 40, 9, 39 C. 39, 40, 46, 56, 9, 27, 38 42. 下列排序算法中， ( 反而最多。A.

14、堆排序 B. 冒泡排序 C. 快速排序 D. 希尔排序43. 设有两个串 p 和 q ， 求 q 在 p 中首次出现的位置的运算称作 ( ) A 连接B. 模式匹配 C. 求子串 D. 求串长44. 下列关键字序列中，构成小根堆的是A. 84, 46 ,62,41,28 , 58, 15 ,37B. 84, 62 ,58,46,41 , 37, 28,15C. 15, 28 ,46,37,84 , 41, 58 ,62D. 15, 28 ,46,37,84 , 58 , 62 ,4145. 散列文件也称为 (A. 顺序文件 C. 直接存取文件 下面关于线性表的叙述中， 线性表采用顺序存储， 线

15、性表采用顺序存储， 线性表采用链接存储， 线性表采用链接存储， 链表不具有的特点是A. 可随机访问任一个元素B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表的长度成正比48. 在有 n 个结点的二叉链表中，值为非空的链域的个数为 A. n-1B. 2n-1C. n+1 D. 2n+1个叶子结点。 （ 当 n=5,6,7 时，叶子1. 一棵深度为 n 的满二叉树有 节点个数？ ）2. 串的三种存储表示： 、堆串存储结构和块链存储结构。3. 数据结构中评价算法的两个重要指标是算法的时间复杂度和 。4. 稀疏矩阵的三元组表表示法的“三元”指的是：该非零元素所在的行下标、

16、该非零元素所在的列下标和 。5. 顺序查找 n 个元素的顺序表 ,当使用监视哨时 , 若查找成功 ,比较关键字的次数 至少为 1 次, 最多为 次。6. 从顺序表中删除一个元素时， 表中所有在被删元素之后的元素均需 一个位置。7. 具有 n 个顶点的有向完全图和无向完全图边的数目分别是 和 。8. 顺序查找法（表长度为 n ）在等概率查找成功时的平均查找长度为 9. 对于有向图而言，其邻接矩阵第 x 行元素之和就是图中第 x 个顶点的 ;邻接矩阵第 x 列元素之和就是图中第 x 个顶点的 10. 已知在一棵含有 N （N>=4 ） 个结点的树中，只有度为 3 的分支结点和 度为 0 的叶子结点，该树含有 个叶子结点。 （ 假定查找每个元素的概率都相等 ）一棵完全二叉树有 999 个结点，它的深度是 对 1000 个数据元素， 希望用最快的速度挑选出前 10 个最大元素， 最好选 的排序方法。11. 以二分查找方法从长度为 6 的有序表中查找一个元素时，查找成功时平均 查找长度为12.13. 用_14. 线性表是由 n （n>=0 ）个同类型数据元素组成的有限序列，具有 、 、 的特点。15. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共 4 个，单 向