当前位置：文档库 › 吉林大学数据结构练习题

吉林大学数据结构练习题

数据结构复习题

一、单项选择题

1. 不带头结点的单链表head为空的判断条件是( )。

A.head==NULL

B.head->next==NULL

C.head->next==head

D.head!=NULL

2. 链表不具有的特点是( )。

A.可随机访问任一元素

B.插入删除不需要移动元素

C.不必事先估计存储空间

D.所需空间与线性表长度成正比

3. 单链表中，增加头结点的目的是为了（）。

A.方便运算的实现

B.用于标识单链表

C.使单链表中至少有一个结点

D.用于标识起始点的位置

4. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是( )。

A.A,B,C,D

B.A,C,D,B

C.D,C,B,A

D.D,A,B,C

5. 栈和队列都是（）。

A.顺序存储的线性表

B.链式存储的线性表

C.限制存取点的线性结构

D.限制存取点的非线性结构

6. 串的长度是（）。

A.串中不同字符的个数

B. 串中不同字母的个数

C.串中所含字符的个数且字符个数大于0

D.串中所含字符的个数

7. 栈和队列的主要区别在于（）。

A.它们的逻辑结构不一样

B.它们的存储结构不一样

C.所包含的运算个数不一样

D.插入删除运算的限定不一样

8. 从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较（）个结点。

A.n

B.n/2

C.(n-1)/2

D.(n+1)/2

9. 线性表是具有n个（）的有限序列。

A. 表元素

B. 字符

C. 数据元素

D. 信息项

10. 某二叉树的前序和后序序列正好相同，则该二叉树一定是（）的二叉树。

A. 空或只有一个结点

B. 高度等于其结点数

C. 任一结点无左孩子

D. 任一结点无右孩子

11. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。

A. 2

B. 1

C. 0

D. –1

12. 下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是（）。

A. 归并排序

B. 直接插入排序

C. 快速排序

D. 冒泡排序

13. 深度为n的二叉树中所含叶子结点的个数最多为（）个。

A.2n

B.n

C.2n-1

D.2n-1

14. 某数组第一个元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是（）。

A.110

B.108

C.100

D.120

15. 串是（）。

A.一些符号构成的序列

B.一些字母构成的序列

C.一个以上字符构成的序列

D.任意有限个字符构成的序列

16. 在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。

A.n

B.n+1

C.n-1

D.n/2

17. 下列四个关键词序列中,（）不是堆。

A.{05,23,16,68,94,72,71,73}

B.{05,16,23,68,94,72,71,73}

C.{05,23,16,73,94,72,71,68}

D.{05,23,16,68,73,71,72,94}

18. 某二叉树的前序和后序序列正好相反，则该二叉树一定是( )的二叉树。

A. 空或只有一个结点

B. 高度等于其结点数

C. 任一结点无左孩子

D. 任一结点无右孩子

19. 在一个单链表中，已知(*q)结点是(*p)结点的前驱结点，若在(*q)和(*p)之间插入(*s)结点,则执行（）。

A.s->next=p->next; p->next=s;

B.p->next=s->next; s->next=p;

C.q->next=s; s->next=p;

D.p->next=s; s->next=q;

20. 设输入序列为的1,2,3,4,借助一个栈可以得到的输出序列是（）。

A.1,3,4,2

B.3,1,4,2

C.4,3,1,2

D.4,1,2,3

21. 二分查找法要求查找表中各元素地键值必须是（）排列。

A. 递增或递减

B. 递增

C. 递减

D.无序

22. 下列排序算法中,某一趟结束后未必能选出一个元素放其最终位置上的是（）。

A. 堆排序

B. 冒泡排序

C. 快速排序

D. 直接插入排序

23. 设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用（）法。

A.冒泡排序

B.快速排序

C.堆排序

D.基数排序

24. 任何一个无向连通图的最小生成树（）。

A. 只有一棵

B. 有一棵或多棵

C. 一定有多棵

D. 可能不存在

25. 3个结点可构成（）个不同形态的二叉树。

A.2

B.3

C.4

D.5

26. 设有6000个无序的元素,希望用最快的速度挑选出其中前6个最大的元

素,最好选用（）法。

A.冒泡排序

B.快速排序

C.堆排序

D.基数排序

27. 某数组第一个元素的存储地址为200，每个元素的长度为4，则第五个元素的地址是（）。

A.210

B.208

C.216

D.220

28. 在一个具有n个顶点的完全无向图的边数为（）。

A.n(n+1)/2

B. n(n-1)/2

C.n(n-1)

D. n(n+1)

29. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为（）。

A.98

B.99

C.50

D.48

30. 在线索二叉树中,结点(*t)没有左子树的充要条件是（）。

A. t->left==NULL

B. t->ltag==1

C.t->ltag==1 && t->left==NULL

D.以上都不对

31. 稀疏矩阵一般采用( )方法压缩存储。

A.三维数组

B.单链表

C.三元组表

D.散列表

32. 设二叉树根结点的层次为0，一棵高度为h 的满二叉树中的结点个数是( )。

A.2h

B.2h-1

C.2h-1

D.2h+1-1

33. 对于键值序列{72,73,71,23,94,16,5,68,76,103}用筛选法建堆，必须从键值为（）的结点开始。

A.103

B. 72

C.94

D.23

34. 在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。

A.1/2

B. 1

C.2

D.4

35. 对有n个记录的有序表采用二分查找，其平均查找长度的量级为（）。

A.O(n)

B. O(nlog2n)

C. O(1)

D. O(log2n)

36．若在线性表中采用折半查找法查找元素，该线性表必须满足（）。

A．元素按值有序B．采用顺序存储结构

C．元素按值有序，且采用顺序存储结构 D．元素按值有序，且采用链式存储结构

37．下面4个序列中，只有（）满足堆的定义。

A. 13,27,49,76,76,38,85,97

B. 76,38,27,49,76,85,13,97

C. 13,76,49,76,27,38,85,97

D. 13,27,38,76,49,85,76,97

38．二维数组A[5][6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[4][5]的存储地址为（）。

A．1140 B．1145 C．1120 D．1125

39．在含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为（）。

A．e B．2e C．n2-e D．n2-2e

40．邻接表的存储结构下图的深度优先遍历类似于二叉树的（）。

A．先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历

二、填空题

1.在双链表中每个结点有两个指针域，一个指向，另一个指向。

2.数据结构的三个方面：数据的、、。

3. 设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为，最多为。

4. 采用二叉链表存储结构，具有n个结点的二叉树一共有个指针域，其中指针域为空。

5. 在有序表(12,24,36,48,60,72,84)中二分查找关键字12时所需进行的关键字比较次数为。

6. 图的存储结构最常用的有和邻接表。

7. 二叉树的存储结构有和链式存储结构。

8. 对于一棵二叉树，设叶子结点数为n0,度为2的结点数为n2,则n0和n2的关是。

9. 一般树的存储结构有双亲表示法、孩子兄弟表示法和。

10. 每个结点只有链接域的链表叫做单链表。

11. 从逻辑关系上讲，数据结构主要分为两大类：线性结构和。

12. 100个结点的完全二叉树的叶子结点数为。

13. 图的存储结构最常用的有和邻接矩阵。

14. 二叉树的存储结构有顺序存储结构和。

15. 一般树的存储结构有双亲表示法、孩子链表表示法和。

16. 二叉树的遍历方式有三种：、和后根遍历。

17. 深度为8的（根的层次号为1）满二叉树有个叶子结点。

18. n个的顶点的连通图的生成树有条边。

19. 如果一个有向图中没有，则该图的全部顶点可以排成一个拓扑序列。

20．下面程序段的时间复杂度是_______ 。

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

a[i][j]=0;

三、应用题

1．根据下图给出的二叉树，求出先序、中序和后序遍历的结点序列。

2. 有二叉树先序序列为：ABCDEF,中序序列为：CBAEDF,试画出该二叉树。

3.给定表（40,36,56,6,64,73,8,23），按数据元素在表中的次序构造一棵二叉查找树，并求其平均查找长度。

4. 试分别画出具有3个结点的树和有具有3个结点的二叉树的所有不同形态。

5. 用普里姆算法(Prim)算法求出下图的最小生成树。

6. 根据下图给出的二叉树，求出先序、中序和后序遍历的结点序列。

7. 已知数据序列为{49,38,65,97,76,13},对该数据序列进行排序，试写出

直接插入排序每趟的结果。

8. 把下图中的二叉树转化为森林。

9. 已知数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出冒泡排序每趟的结果。

10. 已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。

中序序列：c，b，d，e，a，g，i，h，j，f

前序序列：a，b，c，d，e，f，g，h，i，j

四、算法设计题

1. 判断单链表head(head指向表头)是否是递增的。

2. 试设计一算法，删除单链表head(head指向表头)中数据域data的值为x的结点。

3. 假定一棵二叉树用二叉链表存储，试编写求出二叉树中1度结点个数的算法。

4. 假设线性表用带表头结点的单向链表head表示，试写出算法判断单链表head是否是递增的。

5. 编写统计单链表head中，数据域data值为零的结点个数的算法。

吉林大学大学计算机基础题库

吉林大学计算机汇编题库 1.多媒体信息从时效上可分静态和动态媒体两大类，动态媒体包括（A） A.音频、视频和动画 B.音频、文本、图形和图象 C.文本、图形和图象 D.音频、图形和图象 2.下面（A）组设备包括输入设备、输出设备和存储设备 A.鼠标器、绘图仪、光盘 B.磁盘、鼠标器、键盘 C.CRT、CPU、ROM D.磁带、打印机、激光打印机 3.计算机字长取决于（B）总线的宽度 A.通信总线 B.控制总线 C.地址总线 D.数据总线 4.十进制数52转化成二进制数应为（A） A.110100 B.1000000 C.1111110 D.110000 5.磁盘工作时应特别主要避免（B）日光 B.震动 C.刚暗 D.噪声 6.负数的补码是（D）各位求反，然后末位数加1 先对原码中除符号位以外的 B.不对 C.先对符号 D.先对原码 7.目前广泛用于家庭娱乐、科学计算、数据处理和办公自动化的微型计算机属于（C） A.小型机 B.单板机 C.个人计算机 D.单片机 8.要是某台计算机上连接的打印机能被其他计算机所使用，应该将其设置为（B） A.脱机 B.共享 C.暂停 D.默认

https://www.wendangku.net/doc/8712281517.html,B是一种新型（C）接口，主要用于连接各种外部设备 A.芯片内 B.通用并行 C.通用串行 D.芯片间 10.操作系统的特征中，（A）是指两个或两个以上事件在同一时间间隔内发生，从微观上看 A.并发性 B.虚拟性 C.共享性 D.并行性 11.操作系统种类繁多，且各有其特点，但它们的共同特征是并发性、共享性、虚拟性和（D）分时性 B.共存性 C.成批性 D异步性 12.下列叙述中,正确的是D A 硬盘装在主机箱内,因此硬盘属于主存 B储存在任何储存其中的信息,断电后都不会消失 C操作系统只对硬盘进行管理 D盘驱动器属于外部设备 13.计算机网络最突出的作用是D A运算速都快 B储存容量大 C运算精度高 D资源共享 14.将覆盖范围从几十千米到千千米的网络称为A A WAN B LAN C V AN D MAN 15.文本是计算机中基本的信息表示方式，包括C A 语言、歌曲和音乐 B 数字、字母和图形 C 数字、字母、符号和汉字 D 数字、字母和语言 16.用用二为表示实体及实体之间联系的数据型称的D A 网状型 B 混合型 C 称次行 D 关系型 17.多媒体信息从时效上可分静态媒体和动态明天两大类，动态媒体包括A A 音频、视频和动画

数据结构模拟题(开卷)

《数据结构》模拟题（补）一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i

吉林大学网络教育结构力学练习题

结构力学交卷时间：2018-10-20 16:33:07 一、单选题 1. (3分) 图示结构两杆长均为d,EI=常数。则A点的水平位移为( ） ? A. ? B. Pd3/3EI（→） ? C. Pd3/3EI（←） ? D. Pd3/6EI（→）得分：0 知识点：结构力学作业题展开解析答案A 解析 2. (3分) 图示对称结构，其等效半结构为（）

? A. 图（a） ? B. 图（b） ? C. 图（C） ? D. 图（D）得分：0 知识点：结构力学作业题展开解析答案C 解析 3. (3分) 图示结构，求A，B两点相对线位移时，虚拟状态应为( ) ? A. 图（a） ? B. 图（b） ? C. 图（c） ? D. 图（d）得分：0

知识点：结构力学作业题展开解析答案C 解析 4. (3分) 图示结构两杆长均为d,EI=常数。则A点的垂直位移为（） ? A. qd3/2EI（↑） ? B. qd3/3EI（↓） ? C. qd4/4EI（↓） ? D. qd4/6EI（↓）得分：0 知识点：结构力学作业题展开解析答案D 解析 5. (3分) 图示桁架，各杆 EA 为常数，除支座链杆外，零杆数为：( )

? A. 四根； ? B. 二根； ? C. 一根； ? D. 零根。得分：0 知识点：结构力学作业题展开解析答案A 解析 6. (3分) 图示结构，K截面剪力为（） ? A. -10kN ? B. -5kN ? C. 5kN ? D. 10kN 得分：0

知识点：结构力学作业题展开解析答案A 解析 7. (3分) 由于静定结构内力仅由平衡条件决定,故在温度改变作用下静定结构将（）? A. 产生内力 ? B. 不产生内力 ? C. 产生内力和位移 ? D. 不产生内力和位移得分：0 知识点：结构力学作业题展开解析答案B 解析 8. (3分) 对称结构在正对称荷载作用下，在对称切口处有( ) ? A. 正对称的弯矩、剪力和轴力

鹏飞教育自考吉林大学计算机 ————数据结构原理与分析

数据结构原理与分析 1. 具有n个结点的二叉树采用链接结构存储，链表中存放NULL指针域的个数为（n+1）。 2．串是（任意有限个字符构成的序列）。3．在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（2 ）。4．某二叉树的前序和后序序列正好相反，则该二叉树一定是什么二叉树(高度等于其结点数)。 5. 对于栈操作数据的原则是（后进先出）。 6．若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中数据元素的个数是（n-i ）。 7. 在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该(只有左子树上的所有结点 )。 8. 排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( 插入排序 )。 9. 若一棵二叉树具有45个度为2的结点，6个度为1的结点，则度为0的结点个数是（46 ）。 10.某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树(空或只有一个结点)。 11. 在一个有向图中，所有顶点的入度之和等于所有边数（ 4 ）倍。12．串是（任意有限个字符构成的序列）。 13．对于栈操作数据的原则是（后进先出） 14. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是(D,A,B,C )。 15. 结点前序为xyz的不同二叉树，所具有的不同形态为(5 )。 16. 一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的起始地址为100，则该数组的首地址是（70）。 17．在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(2h )。 18. 在一个无向图中，所有顶点的度数之和等于所有边数（ 2 ）倍。 19.因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 (d ). 20. 一般情况下，将递归算法转换成等价的非递归算法应该设置（堆栈）。21. 对于一棵满二叉树，m个树叶，n 个结点，深度为h,则(n=2h＋1-1 )。 22. 线性表的长度是指（表中的元素个数）。 23. 用邻接表表示图进行深度优先遍历时，通常用来实现算法的辅助结构是(栈 )。 24. 堆的形状是一棵(完全二叉树 )。 25. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ cabdef）。 26. 若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是（ C. 1≤i≤n）。 27．在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（2 ）。28. 若某线性表中最常用的操作是取第i个元素和删除最后一个元素，则采用什么存储方式最节省时间（顺序表）。 29．一组记录的关键字为{45, 80, 55, 40, 42, 85}，则利用堆排序的方法建立的初始堆为（85, 80, 55, 40, 42, 45 ）。 30. 如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2中结点的（先根序列）。 31. 对于一棵满二叉树，m个树叶，n 个结点，深度为h,则(n=2h＋1-1 )。32.具有n个顶点的有向图最多可包含的有向边的条数是(n(n-1) )。 33．设有6000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用(堆排序)法。 34.任何一个无向连通图的最小生成树(有一棵或多棵 )。 35. 排序方法中，从未排序序列中挑选元素，将其放入已排序序列的一端的方法，称为(选择排序)。 36. 对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（R[6]，R[2]，R[4]，R[3] ）。 37. 因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 (d )。 38.深度为h且有多少个结点的二叉树称为满二叉树(2h+1-1 )。39．某二叉树的前序和后序序列正好相反，则该二叉树一定是的二叉树为(高度等于其结点数)。 40. 带头结点的单链表head为空的判断条件是(head->next==NULL)。41．栈和队列的主要区别在于（插入删除运算的限定不一样） 42. 设高度为h的二叉树上只有度为0 和度为2的结点，则此类二叉树中所包含的结点数至少为(2h-1 )。 43．在一个单链表中，若删除(*p)结点的后继结点，则执行 (p->next=p->next->next)。 44.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（n+1 ） 45.若一棵二叉树有11个度为2的结点，则该二叉树的叶结点的个数是（12 ）。 46. 对有n个记录的表按记录键值有序建立二叉查找树，在这种情况下，其平均查找长度的量级为（O(n) ）。 47. 有向图中，以顶点v为终点的边的数目，称为顶点v的（入度）。 48. 链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况)。 49. 若频繁地对线性表进行插入和删除操作，该线性表应该采用的存储结构是（链式）。 50. 设一个栈的输入序列是 1，2，3， 4，5,则下列序列中，是栈的合法输出序列的是（3 2 1 5 4）。 51.设森林F中有三棵树，第一、第二和第三棵的结点个数分别为m1,m2和 m3,则森林F对应的二叉树根结点上的右子树上结点个数是 ( m2+m3 )。 52. 有数据{53，30，37，12，45，24， 96}，从空二叉树开始逐个插入数据来形成二叉查找树，若希望高度最小，则应选择下面输入序列是（ 37,24,12,30,53,45,96）。 53．若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向(各自的尾结点 )。 54. 二叉树的第I层上最多含有结点数为（2I ）。 55.设高度为h的二叉树上只有度为0 和度为2的结点，则此类二叉树中所包含的结点数至少为（2h-1 ）。 56.如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2 中结点的（先根序列）。 57. 用分划交换排序方法对包含有n个关键的序列进行排序，最坏情况下执行的时间杂度为(O(n2))。 58. 有n个叶子的哈夫曼树的结点总数为（2n-1 ）。 59. 稀疏矩阵一般采用的压缩存储方法为(三元组表)。 60. 若二叉树中度为2的结点有15个，度为1 的结点有10个，则叶子结点的个数为（16 ）。 61. 若某完全二叉树的深度为h，则该完全二叉树中具有的结点数至少是(2h －1 )。 62. 任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置 (肯定不发生变化)。 63.初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为( n-1)。 64. 对有n个记录的有序表采用二分查找，其平均查找长度的量级为 (O(log2n))。 65用冒泡排序法对序列 {18,16,14,12,10,8}从小到大进行排序，需要进行的比较次数是(15 )。 66在一个有向图中，所有顶点的出度之和等于所有边数的倍数是（ 1 ）。 67.有n个顶点的图采用邻接矩阵表示，则该矩阵的大小为（n*n ）。 68.6个顶点的无向图成为一个连通图至少应有边的条数是（5 ）。 69. 对有14个数据元素的有序表R[14] 进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（R[6]，R[4]，R[2]，R[3]）。 70. 串是（任意有限个字符构成的序列）。 71.个无向图中，所有顶点的度数之和等于所有边数（1 ）倍。 72.单链表表示的链式队列的队头在链表的什么位置（链头）。 73. 一组记录的关键字为{45, 80, 55, 40, 42, 85}，则利用堆排序的方法建立的初始堆为（85, 80, 55, 40, 42, 45 ）。 74. 对于一棵满二叉树，m个树叶，n 个结点，深度为h,则(n=2h＋1-1) 75.某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树 (空或只有一个结点)。 76.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（n+1 ）。 77. 若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动表中元素的个数是（n-i+1）。 78. 树中所有结点的度等于所有结点数加（-1 ）。 79.设二叉树根结点的层次为0，一棵高度为h 的满二叉树中的结点个数是 (2h+1-1 )。 80. 将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点(有左孩子，无右孩子)。 81. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为 ( BA+180 )。 82.在一个具有n个顶点的完全无向图的边数为 (n(n-1)/2 )。 83．设森林F中有三棵树，第一、第二和第三棵的结点个数分别为m1,m2和 m3,则森林F对应的二叉树根结点上的右子树上结点个数是 (m2+m3 )。 84.对于键值序列 {72,73,71,23,94,16,5,68,76,103}用筛选法建堆，开始结点的键值必须为 (94 )。 85. 在图形结构中，每个结点的前驱结点数和后续结点数可以有(任意多个 )。 86.对有n个记录的有序表采用二分查找，其平均查找长度的量级为 (O(log2n) )。 87. 用孩子兄弟链表表示一棵树，若要找到结点x的第5个孩子，只要先找到 x的第一个孩子，然后(从兄弟域指针连续扫描4个结点即可)。 88．有一个有序表为{1，3，9，12，32， 41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功的比较次数是（4 ）。. 89. 当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为(n-1 )。 90.深度为h的满二叉树具有的结点个数为（2h+1-1 ）。 91. 二维数组A[5][6]的每个元素占5 个单元，将其按行优先顺序存储在起始地址为3000的连续的内存单元中，则元素A[4][5]的存储地址为（3145）。 92.一个具有n个顶点e条边的无向图中，采用邻接表表示，则所有顶点的邻接表的结点总数为（2e ）。 93. 一个具有n个顶点的图采用邻接矩阵表示，则该矩阵的大小为（n*n）。 94. 一个具有n个顶点e条边的无向图中，采用邻接表表示，则所有顶点的邻接表的结点总数为（ 2e ）。 95. 若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向 ( 各自的尾结点)。 96．在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(2h )。 97. 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用比较次数最少的方法是（直接插入排序）。 98. 有n个叶子的哈夫曼树的结点总数为（2n-1 ）。 99.二分查找法要求查找表中各元素的键值必须是(递增或递减 )。 100. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂性为（ ()n ）。 101.链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况 )。 102. 将长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为(O(n) )。 103.若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（直接插入排序）方法比较次数最少。 104. 若字符串“1234567”采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节，则该字符串的存储密度为（33.3﹪）。 105.用分划交换排序方法对包含有n个关键的序列进行排序，最坏情况下执行的时间杂度为(O(n2) )。 106. 若在一棵非空树中，某结点A有3 个兄弟结点（包括A自身），B是A的双亲结点，则B的度为（3）。 107. 单链表中，增加头结点的目的是为了（方便运算的实现）。 108. 深度为h的满二叉树所具有的结点个数是（2h+1-1 ）。 109．按照二叉树的定义,具有3个结点的二叉树有多少种(5 )。 110. 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为(O(n) )。 111．树中所有结点的度等于所有结点数加（-1 ）。 112. 树中所有结点的度等于所有结点数加（ -1 ） 113. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是(ZXY )。 114. 用邻接表表示图进行深度优先遍历时，通常采用的辅助存储结构是 (栈)。 115. 对有18个元素的有序表作二分（折半）查找，则查找A 3的比较序列的下标为（9、4、2、3）。 116. 在含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为（ n2-2e）。 117. 树形结构的特点是：一个结点可以有 ( 多个直接后继)。 118. 使具有30个顶点的无向图成为一个连通图至少应有边的条数是（29）。 119. 按照二叉树的定义,具有3个结点的二叉树具有的种类为(5 )。 120. 使具有9个顶点的无向图成为一个连通图至少应有边的条数是（8 ）。 121. 在顺序表（n足够大）中进行顺序查找，其查找不成功的平均长度是（n+1 ）。 122. 设树T的度为4，其中度为1，2， 3和4的结点个数分别为4，2，1，1 则 T中的叶子数为（ 8 ）。 123. 栈的插入和删除操作进行的位置在（栈顶）。 124. 某二叉树的前序和后序序列正好相同，则该二叉树一定是的二叉树为 (空或只有一个结点)。 125. 链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况)。 126. 对稀疏矩阵进行压缩存储是为了（节省存储空间）。 127. 结点前序为xyz的不同二叉树，所具有的不同形态为(5 )。 128. 若一棵二叉树具有20个度为2的结点，6个度为1的结点，则度为0的结点个数是（21 ）。 129. 一棵线索二叉树的线索个数比链接个数多（ 2 ）个。 1. 若一棵二叉树有10个叶结点，则该二叉树中度为2的结点个数为9。 2．在有序表(12,24,36,48,60,72,84) 中二分查找关键字72时所需进行的关键字比较次数为2。 3.对于一棵二叉树，设叶子结点数为n0, 次数为2的结点数为n2,则n0和n2的关系是n0= n2＋1。 4. 在循环链表中，从任何一结点出发都能访问到表中的所有结点。 5. 普里姆(Prim)算法适用于边稠密图。 6.深度为h且有2k-1个结点的二叉树称为满二叉树。(设根结点处在第1层)。 7.图的深度优先搜索方法类似于二叉树的先序遍历。 8.哈夫曼树是带权路径长度最小的二叉树。 9. 二叉树的存储结构有顺序存储结构和链式存储结构。 10. 哈夫曼树是带权路径长度最小的二叉树。 11.一般树的存储结构有双亲表示法、孩子兄弟表示法和孩子链表表示法。 12. 将数据元素 2,4,6,8,10,12,14,16,18,20依次存于一个一维数组中，然后采用折半查找元素12，被比较过的数组元素的下标依次为5，7，6 。。 13. 图的深度优先遍历序列不是唯一的。 14. 下面程序段的时间复杂度是 O （mn）。 for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j]=0; 16. 图的遍历是指从图中某一顶点出发访问图中全部顶点且使每一顶点仅被访问一次。 17. 在一个图中，所有顶点的度数之和等于所有边的数目的2倍。 18. 由一棵二叉树的后序序列和中序序列可唯一确定这棵二叉树。 19. 在有序表(12,24,36,48,60,72,84) 中二分查找关键字72时所需进行的关键字比较次数为2。 20. 若二叉树的一个叶子结点是某子树的中根遍历序列中的第一个结点，则它必是该子树的后跟遍历中的第一个结点。 21.在直接插入排序、直接选择排序、分划交换排序、堆排序中稳定的排序方法有直接插入排序。 22.具有100个结点的完全二叉树的叶子结点数为50。 23.普里姆(Prim)算法适用于边稠密图。 24. 在n个结点的顺序表中插入一个结点需平均移动 n/2 个结点。 25.将一棵树转换成一棵二叉树后，二叉树根结点没有右子树。 26循环队列的引入，目的是为了克服假溢出。 27.若连通网络上各边的权值均不相同，则该图的最小生成树有1棵。 28．在有序表(12,24,36,48,60,72,84) 中二分查找关键字72时所需进行的关键字比较次数为2 。 29.栈和队列的共同特点是插入和删除均在端点处进行。 30. 二叉树的遍历方式有三种：先序遍历、中序遍历、后序遍历。 31. 若连通图的顶点个数为n，则该图的生成树的边数为n-1。 32.图的存储结构最常用的有邻接矩阵和邻接表。 33. 若一棵二叉树有15个叶结点，则该二叉树中度为2的结的点个数为14。 34．队列中允许进行插入的一端称为队尾。 35.拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在环。 36.在有序表(15,23,24,45,48,62,85) 中二分查找关键词23时所需进行的关键词比较次数为2。 37. 则高度为k的二叉树具有的结点数目，最少为k，最多为2k-1。 38. 若连通网络上各边的权值均不相同，则该图的最小生成树有1棵。 39. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是3 1 2。 40. 设有一个顺序栈S，元素S1，S2， S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5， S1，则顺序栈的容量至少应为 3 。 41. 对于一棵二叉树，设叶子结点数为 n0,次数为2的结点数为n2,则n0和n2 的关系是 n0= n2＋1 。 42. 设某二叉树的后序遍历序列为 ABKCBPM，则可知该二叉树的根为 M 。 43. 数据结构的三个方面：数据的逻辑结构、物理结构、运算。 44. 每个结点只有一个链接域的链表叫做单链表。 45. 设无向图G的顶点数为n，则要使 G连通最少有 n-1条边。 46. 组成串的数据元素只能是字符。 47．图的存储结构最常用的有邻接表和邻接矩阵。 48. 由一棵二叉树的后序序列和中序序列可唯一确定这棵二叉树。 49. 队列中允许进行插入的一端称为队尾。 1.对于一个队列，如果输入项序列由 1,2,3,4所组成，试给出全部可能的输出序列。答：1,2,3,4。 2. 已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。中序序列：c，b，d，e，a，g，i，h， j，f 前序序列：a，b，c，d，e，f，g，h， i，j 答：该二叉树的后序序列为： c,e,d,b,i,j,h,g,f,a 3. 为什么说树是一种非线性结构？答：树中的每个结点除了根结点外，其余每个结点有一个直接前驱，但有多个直接后继，所以说树是一种非线性结构。 4．将算术表达式a+b*（c+d/e）转为后缀表达式。答： B．abcde/+*+ 5. 找出所有这样的二叉树形，其结点在先根次序遍历和中根次序遍历下的排列是一样的。答：为空树，或为任一结点至多只有右子树的二叉树。 8.有 n 个顶点的无向连通图至少有多少条边？有 n 个顶点的有向连通图至少有多少条边？答：有 n 个顶点的无向连通图至少有 n-1条边，有 n 个顶点的有向连通图至少有n条边。 9．下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问，哪些排序方法是稳定的？答：起泡排序, 直接插入排序，归并排序是稳定的。 10. 完全二叉树用什么数据结构实现最合适，为什么？答：完全二叉树用一维数组实现最合适。因为完全二叉树保存在一维数组中时，数组内没有空洞，不存在空间浪费问题；另外，顺序存储方式下，父子结点之间的关系可用公式描述，即已知父（或子）结点寻找子（或父）结点只需计算一个公式，访问结点方便。但采用链表存储时就存在空间浪费问题，因为每个结点要另外保存两个链接域，并且寻找结点也不容易。 11．线性表有两种存储结构：一是顺序表，二是链表。试问：如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？答：选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。 12．试述顺序存储和链式存储的区别及各自的优缺点。答：数组占用连续的内存空间，链表不要求结点的空间连续。 1）插入与删除操作：由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改变一些指针的链接，因此，链表比数组易于实现数据的插入和删除操作。 2）内存空间的占用情况：因链表多了一个指针域，故较浪费空间，因此，在空间占用方面，数组优于链表。 3）数据的存取操作：访问链表中的结点必须从表头开始，是顺序的存取方式，而数组元素的访问是通过数组下标来实现的，是随机存取方式，因此，在数据存取方面，数组优于链表。数据的合并与分离：链表优于数组，因为只需要改变指针的指向 13. 将表达式 ((a+b)-c*(d+e)-f)*(g+h)改写成后缀表达式。答：后缀表达式为：ab+cde+*-f-gh+* 19.写出中缀表达式A-(B+C/D)*E的后缀形式。答：中缀表达式A-(B+C/D)*E的后缀形式是：ABCD/+E*-。 20．为什么用二叉树表示一般树？答：树的最直观表示是为树中结点设置指向子结点的指针域，对k叉树而言，每个结点除data域外，还有k个链接域。这样，对一个有n个结点的k叉树来说，共有n*k个指针域，其中n-1个不空，另外n(k-1)+1个指针域为空，因此，空链接域的比例约为（k-1）/k ，于是导致大量的空间浪费。然而，如果采用二叉树表示一棵n个结点的树，则树中共有2n个链接域，其中未用到的有n+1个，占所有指针域的比例约为 1/2，空间浪费少很多。另外，因为任何树型结构都可以转换成二叉树，因此，通常用二叉树表示树型结构。 21．已知数据序列为 12,5,9,20,6,31,24，对该数据序列进行排序，试写出冒泡排序每趟的结果。答：初始键值序列12 5 9 20 6 31 24 第一趟排序 [5 9 12 6 20 24] 31 第二趟排序 [5 9 6 12 20] 24 31 第三趟排序 [5 9 6 12] 20 24 31 第四趟排序 5 6 9 12 20 24 31 22．试找出前序序列和中序序列相同的所有二叉树。解答：空树或缺左子树的单支树。 23．完全二叉树用什么数据结构实现最合适，为什么？答：完全二叉树用一维数组实现最合适。因为完全二叉树保存在一维数组中时，数组内没有空洞，不存在空间浪费问题；另外，顺序存储方式下，父子结点之间的关系可用公式描述，即已知父（或子）结点寻找子（或父）结点只需计算一个公式，访问结点方便。但采用链表存储时就存在空间浪费问题，因为每个结点要另外保存两个链接域，并且寻找结点也不容易。 26．我们已经知道，树的先根序列与其对应的二叉树的先根序列相同，树的后根序列与其对应的二叉树的中根序列相同。那么利用树的先根遍历次序与后根遍历次序，能否唯一确定一棵树？请说明理由。答：能。因为树的先根序列与其对应的二叉树的先根序列相同，树的后根序列与其对应的二叉树的中根序列相同，而二叉树的先根序列与二叉树的中根序列能唯一确定一棵二叉树，所以利用树的先根遍历次序与后根遍历次序，能唯一确定一棵树。 28．已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。中序序列：c，b，d，e，a，g，i，h， j，f 前序序列：a，b，c，d，e，f，g，h， i，j 答：该二叉树的后序序列为： c,e,d,b,i,j,h,g,f,a 29．对半查找是否适合于以链接结构组织的表？答：对半查找不适合于以链接结构组织的表。。 30. 请指出中序遍历二叉查找树的结点可以得到什么样的结点序列。答：中序遍历二叉查找树的结点就可以得到从小到大排序的结点序列。 31．已知数据序列为 12,5,9,20,6,31,24，对该数据序列进行排序，试写出归并排序每趟的结果。解答：初始键值序列12 5 9 20 6 31 24 第一趟排序 [5 12] [9 20] [6 31] [24] 第二趟排序 [5 9 12 20] [6 24 31] 第三趟排序 5 6 9 12 20 24 31（） 37.一组记录的关键字为(52, 56, 26, 12, 69, 85, 33, 48, 70)，给出快速排序的过程。解答：解：52, 56, 26, 12, 69, 85, 33, 48, 70 第一趟排序 33, 48, 26, 12, 52, 85, 69, 56, 70 第二趟排序 26, 12, 33, 48, 52, 69, 56, 70, 85 第三趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85 第四趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85 第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85 38．下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直 1

数据结构模拟试题及答案

数据结构模拟试题一一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

《数据结构C》模拟试题

山东科技大学继续教育学院《数据结构C》模拟试题一班级姓名学号一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。

《数据结构》模拟试卷一及答案

模拟试卷一一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )