《数据结构》习题汇编08_第八章_查找_试题

数据结构课程（本科）第七章试题

一、单项选择题

1.若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为

（）。

A. n

B. n+1

C. (n-1)/2

D. (n+1)/2

2.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概

率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（）。

A. 5.5

B. 5

C. 39/8

D. 19/4

3.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索

第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（）。

A. 5/3

B. 2

C. 7/3

D. 4/3

4.对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度

为（）。

A. n/2

B. (n+1)/2

C. (n-1)/2

D. n/4

5.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值

的向上取整。

A. log2(n+1)

B. log2n

C. n/2

D. (n+1)/2

6.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值

的向下取整加一。

A. log2(n+1)

B. log2n

C. n/2

D. (n+1)/2

7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）

的值除以9。

A. 20

B. 18

C. 25

D. 22

8.对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（）。

A. 3

B. 4

C. 5

D. 6

9.对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（）。

A. O(n)

B. O(n2)

C. O(1)

D. O(log2n)

10.在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（）。

A. n

B. log2n

C. (h+1)/2

D. h+1

11.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为

（）。

A. O(n)

B. O(1)

C. O(log2n)

D. O(n2)

12.从具有n个结点的二叉搜索树中搜索一个元素时，在最坏情况下进行成功搜索的时间复杂度为

（）。

A. O(n)

B. O(1)

C. O(log2n)

D. O(n2)

13.向具有n个结点的二叉搜索树中插入一个元素时，其时间复杂度大致为（）。

A. O(1)

B. O(log2n )

C. O(n)

D. O(n log2n)

14.在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的平衡因子的取值围是（）。

A. -1～1

B. -2～2

C. 1～2

D. 0～1

15.向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的调整过程，此调

整分为（）种旋转类型。

A. 2

B. 3

C. 4

D. 5

16.向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的左单或右单旋转

的调整过程，此时需要修改相关（）个结点指针域的值。

A. 2

B. 3

C. 4

D. 5

17.向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的双向旋转的调整

过程，此时需要修改相关（）个结点指针域的值。

A. 2

B. 3

C. 4

D. 5

参考答案： 1. D 2. C 3. A 4. B 5. A

6. B

7. C

8. A

9. D 10. D

11. C 12. A 13. B 14. A 15. C

16. A 17. C

二、填空题

1.以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为________。

2.对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为p i，搜索长度（即在搜索过程中依次

同有关元素比较的总次数）为c i，则在搜索成功情况下的平均搜索长度的计算公式为________。

3.假定一个顺序表的长度为40，并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长

度为________。

4.以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为________。

5.从有序表 (12, 18, 30, 43, 56, 78, 82, 95) 中折半搜索元素56时，其搜索长度为________。

6.假定对长度n = 50的有序表进行折半搜索，则对应的判定树中最后一层的结点数为______个。

7. 从一棵二叉搜索树中搜索一个元素时，若给定值小于根结点的值，则需要向________继续搜索。

8. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向________继续搜索。

9. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值小于根结点的值，则应把它插入到根结点的

________上。

10. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值大于根结点的值，则应把它插入到根结点的

________上。

11. 向一棵二叉搜索树________一个元素时，若查找到的根结点为空值，则应把该元素结点到这个空指针

位置上。

12. 根据n 个元素建立一棵二叉搜索树的时间复杂度性大致为_____________。

13. 在一棵AVL 树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超

过________。

14. 根据一组记录 ( 56, 42, 50, 64, 48 ) 依次插入结点生成一棵AVL 树（高度平衡的二叉搜索树）时，

当插入到值为_______的结点时需要进行旋转调整。

15. 根据一组记录 ( 56, 74, 63, 64, 48 ) 依次插入结点生成一棵AVL 树（高度平衡的二叉搜索树）时，

当插入到值为63的结点时需要进行________________调整。

16. 根据一组记录 ( 56, 42, 38, 64, 48 ) 依次插入结点生成一棵AVL 树（高度平衡的二叉搜索树）时，

当插入到值为38的结点时需要进行____________调整。

17. 根据一组记录 ( 56, 42, 73, 50, 64, 48, 22 ) 依次插入结点生成一棵AVL 树（高度平衡的二叉搜

索树）时，当插入到值为_______的结点时才出现不平衡，需要进行旋转调整。

18. 在一棵AVL 树（高度平衡的二叉搜索树）上进行插入或删除元素时，所需的时间复杂度为_________。

参考答案： 1. O(n)

2. ∑-=10

n i i

i c

p 3. 20.5 4. O(log 2n) 5. 3

6. 19

7. 左子树

8. 右子树 9. 左子树 10. 右子树 11. 插入

12. O(nlog 2n)

13. 1 14. 50

15. 先右后左双旋转 16. 右单旋转

17. 48

18. O(lon 2n)

三、判断题

1. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，

则可得到最小的平均搜索长度。

2.进行折半搜索的表必须是顺序存储的有序表。

3.能够在存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。

4.假定用两个有序单链表表示两个集合，则这两个集合交运算得到的集合单链表，其长度小于参加运算

的任一个集合单链表的长度。

5.假定用两个有序单链表表示两个集合，则这两个集合的差运算得到的集合单链表，其长度小于参加运

算的任一个集合单链表的长度。

6.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树（它的特点是除最底层结

点外其他各层结点数都是满的，最底层的若干结点可能散布在该层各处）。

7.对二叉搜索树进行前序遍历得到的结点序列是一个有序序列。

8.在由n个元素组成的有序表上进行折半搜索时，对任一个元素进行搜索的长度（即比较次数）都不会

大于log2n+1。

9.根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(log2n)。

10.根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(nlog2n)。

11.对于同一组记录，若生成二叉搜索树时插入记录的次序不同则得到不同结构的二叉搜索树。

12.对于同一组记录，生成二叉搜索树的结构与插入记录的次序无关。

13.对于两棵具有相同记录集合而具有不同结构的二叉搜索树，按中序遍历得到的结点序列是相同的。

14.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优

二叉搜索树。

15.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优

二叉搜索树。

参考答案： 1. 是 2. 是 3. 否 4. 是 5. 否

6. 是

7. 否

8. 是

9. 否10. 是

11. 是12. 否13. 是14. 是15. 否

四、运算题

1.一个一维数组a[10]中存储着一个有序表，该有序表为：(15, 26, 34, 39, 45, 56, 58, 63, 74, 76 )，

根据折半搜索所对应的判定树，写出该判定树的广义表表示，并求出在等概率情况下搜索成功的平均搜索长度。

判定树的广义表表示：_______________________________ 平均搜索长度：_________________

2. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]

中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

元素值 比较次数

3. 假定一个线性序列为 ( 38, 52, 25, 74, 68, 16, 30, 54, 90, 72 )，根据此线性序列中元素的排列

次序生成一棵二叉搜索树，求出对该二叉搜索树查找38, 74, 68, 30, 72等元素时的比较次数。

待查元素： 比较次数：

4. 假定一个线性序列为 ( 56, 27, 34, 95, 73, 16, 50, 62, 65 )，根据此线性序列中元素的排列次序

生成一棵二叉搜索树，求出该二叉搜索树的高度（假定树根结点的高度为0）、度为2的结点个数和叶子结点个数。

高度：_____________

度为2的结点个数：____________ 叶子结点个数：____________

5. 假定一个线性序列为 ( 38, 42, 55, 15, 23, 44, 30, 74, 48, 26 )，根据此线性序列中元素的排列

次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点和右子树为空的所有单支结点，请按从小到大的次序排列写出。

左子树为空的所有结点：____________ 右子树为空的所有结点：____________

6. 已知一棵二叉搜索树的广义表表示为：28 (12 ( , 16), 49 (34 (30), 72 (63) ) )，按主教材介绍

的删除算法，求出从中依次删除72, 12, 49, 28结点后得到的二叉搜索树的广义表表示。

广义表表示：_____________________________

7. 假定一组数据对象为 ( 40, 28, 16, 56, 50, 32, 30, 63 )，按次序插入每个对象生成一棵AVL 树（高

度平衡的二叉搜索树），根据插入过程填写下表，在相应位置填写所需要的调整类型：“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，若不需要旋转则填写“无”。

数据： 调整：

8. 假定一组数据对象为 ( 40, 28, 16, 56, 50, 32, 30, 63, 44, 38 )，按次序插入每个对象生成一棵

AVL 树（高度平衡的二叉搜索树），请回答插入后需调整的结点个数和插入后不调整的结点个数。

34 56 58 63 94 38 74 68 30 72 40 28 16 56 50 32 30 63

插入时伴随旋转调整的结点个数：___________ 插入不调整的结点个数：__________

9. 假定一组记录为 ( 36, 75, 83, 54, 12, 67, 60, 40 )，按次序插入每个结点生成一棵AVL 树（高度

平衡的二叉搜索树），请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少？

左单旋转结点个数：____________ 右单旋转结点个数：____________

先左后右双旋转结点个数：___________ 先右后左双旋转结点个数：___________ 不调整结点个数：____________

10. 假定一组记录为 ( 38, 42, 55, 15, 23, 44, 30, 74, 48, 26 )，按次序插入每个结点生成一棵AVL

树（高度平衡的二叉搜索树），给出最后得到的AVL 树中度为2、度为1和度为0的结点个数。

度为2的结点个数：__________ 度为1的结点个数：__________ 度为0的结点个数：__________

参考答案：

1. 判定树的广义表表示：45 (26 (15, 34 ( , 39 ) ), 63 ( 56 ( , 58 ), 74 ( , 76 ) ) ) //4

分

平均查找长度：29/10

//2分

2. 判断结果

元素值

比较次数

//对1个给1分，全对给6分

3. 判断结果

待查元素： 比较次数：

//对1个给1分，全对给6分

4. 高度：4

//2分 度为2的结点个数：2 //2分 叶子结点个数：3 //2分

5. 左子树为空的结点：15, 23, 42, 44

//全对4分，否则不得分 右子树为空的结点：30

//2分

6. 广义表表示：30 (16 , 63 (34) )

7. 插入结果和调整类型为

34 56 58 63 94 02 1 3 4 4 38 74 68 30 72 01 3 4 3 5

数据结构与算法考试大纲

《数据结构》考试大纲 I.考查目标 考试目标是了解常见数据结构的概念，掌握数据结构的构造方法以及相应的算法思想，会对重点数据结构的操作方法和算法进行简单的伪代码编写。 II.考试形式和试卷结构 一、试卷总分及考试时间 试卷总分为150分，考试时间180分钟。 二、答题方式 答题方式为闭卷、笔试。 III．考查内容 第一章、线性表 1.线性表的逻辑结构 2.线性表的顺序存储结构 3.线性表的链式存储结构 3.1单链表 3.2循环链表 3.3双向链表 第二章、栈与队列

1.栈 1.1栈的基本概念 1.2顺序栈 1.3链式栈 2.队列 2.1队列的基本概念 2.2链队列 2.3循环队列——队列的顺序存储结构第三章、串 1.串类型的定义 2.字符串的实现 3.字符串模式匹配算法 3.1简单字符串模式匹配算法 3.2首尾字符串模式匹配算法 3.3KMP模式匹配算法 第四章、数组和广义表 1.数组 1.1数组的基本概念 1.2数组的顺序存储方式 2.矩阵 2.1矩阵的定义和操作

2.2特殊矩阵 2.3稀疏矩阵 3.广义表 3.1基本概念 3.2广义表的存储结构 第五章、树和二叉树 1.树的基本概念 1.1树的定义 1.2基本术语 2.二叉树 2.1二叉树的定义 2.2二叉树的性质 2.3二叉树的存储结构 3.二叉树的遍历 3.1遍历的定义 3.2遍历算法 4.树和森林 4.1树的存储表示 4.2森林的存储表示 4.3树和森林的遍历 4.4树和森林与二叉树的转换 5.哈夫曼树与哈夫曼编码

5.1哈夫曼树的基本概念 5.2哈夫曼树构造算法 5.3哈夫曼树编码 第六章、图 1.图的定义和术语 2.图的存储表示 2.1邻接矩阵 2.2邻接表 3.图的遍历 3.1深度优先搜索 3.2广度优先搜索 4.图的最小代价生成树 4.1Prim算法 4.2Kruskal算法 5.有向无环图的应用 5.1拓扑排序 5.2关键路径 6.最短路径问题 6.1单源点最短路径 6.2所有顶点之间的最短路径第七章、查找

数据结构模拟题(开卷)

《数据结构》模拟题（补） 一．单项选择题 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

事业单位考试公共基础知识题库及答案

事业单位考试公共基础知识题库及答案 1、CNSS是()的简称。 A、中国北斗卫星导航系统 B、俄罗斯全球卫星导航系统 C、美国的全球定位系统 D、欧洲伽利略定位系统 A、人的感觉受理性指导 B、人的认识具有能动性 C、理性认识是感性认识的基础 D、已有的认识影响感觉活动 A、受教育权 B、财产权 C、继承权 D、劳动权 4、决策是一项包括多个步骤的系统工作，其最后一个步骤是()。 A、监督与反馈 B、选择备选方案 C、界定问题C、设立决策准则 5、正当防卫必须在侵害行为正在进行时，迫不得已的情况下进行，而紧急避险不强调迫不得已。() A、正确 B、错误 6、土地承包经营权属于用益物权。() A、正确 B、错误 1、【答案】A。解析：北斗卫星导航系统(CompassNavigationSatelliteSystem)简称CNSS。俄罗斯全球卫星 导航系统简称是GLONASS;美国的全球定位系统简称是GPS;欧洲伽利 略定位系统(GalileoPositioningSystem)，是欧盟一个正在建造中 的卫星定位系统，有“欧洲版GPS”之称，简称“伽利略计划”。 故本题答案为A。 3、【答案】BC。解析：所谓积极受益权，是指公民可以积极主 动地向提出请求，也应积极予以的权利。除了财产权和继承权外， 公民享有的其他社会经济、文化教育权利、劳动权、劳动者休息权、

物质帮助权和受教育权等都属于积极受益权。与积极受益权相对的 是消极受益权，是指公民行使该项权利一般不需要积极的，仅负有 不侵犯其合法行使以及该项权利受到侵害时予以救济的义务。故B、C选项当选。 4、【答案】A。解析：一个好的决策一般可通过7个步骤而得到：对问题的精确界定;详细界定此项决策必须满足的要求;找出所有备 选方案;分析每种备选方案的风险与后果及其边界条件;做出决策;执 行决策;建立反馈：跟进与后续行动。 6、【答案】A。解析：土地承包经营权是一种新型的用益物权。所以本题正确。 1、土地革命战争时期，毛泽东指出：“一国之内，在四周白色 政权的包围中，有一小块或若干小块红色政权的区域长期的存在， 这是世界各国从来没有的事。这种奇事的发生，有其独特的原因。”红色政权能够长期存在和发展的根本原因是()。 B、国民革命的政治影响及良好的群众基础 C、全国革命形势的继续发展 D、相当力量的正式红军的存在以及共产党组织的坚强有力和正 确的领导 2、事业单位受聘人员连续旷工超过()个工作日或者1年内累计 旷工超过30个工作日的，聘用单位可以随时单方面解除聘用合同。 A、5 B、8 C、10 D、15 3、属于微观经济政策的是()。 A、产业政策 B、价格政策 C、货币政策 D、财政政策 5、下列说法中，有助于提升从业人员职业道德的观点是()。(多选) A、“舟必漏而后入水，土必湿而后生苔” B、“运筹帷幄之中，千里之外”

数据结构试卷带答案

数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i

991数据结构与C语言程序设计考试大纲(2013版).

编程技术精品！ 991数据结构与C语言程序设计考试大纲（2013版） 2013年《数据结构与C语言程序设计》考试内容包括"数据结构"与"C语言程序设计"两门课程的内容，各占比例50%，试卷满分为150分。《数据结构》部分指定参考书：《数据结构教程（第二版）》唐发根编著北京航空航天大学出版社一、概述 1．数据的逻辑结构与存储结构的基本概念； 2．算法的定义、基本性质以及算法分析的基本概念，包括采用大?形式表示时间复杂度和空间复杂度。二、线性表 1．线性关系、线性表的定义，线性表的基本操作； 2．线性表的顺序存储结构与链式存储结构(包括单(向链表、循环链表和双向链表的构造原理； 3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计。三、堆栈与队列 1．堆栈与队列的基本概念与基本操作； 2．堆栈与队列的顺序存储结构与链式存储结构的构造原理； 3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计； 4．堆栈和队列在解决实际问题中应用。四、树与二叉树 1．树与二叉树的基本概念，基本特征、名词术语； 2．完全二叉树与满二叉树的基本概念，二叉树的基本性质； 3．二叉树与树、树林之间的转换； 4．二叉树的顺序存储结构与二叉链表存储结构； 5．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，以及在二叉链表基础上各种遍历算法(重点为非递归算法的设计与应用； 6．二叉排序树的基本概念、建立(插入、查找与平均查找长度ASL 的计算； 7．哈夫曼(Huffman树的基本概念，哈夫曼树的构造与带权路径长度(WPL的计算。五、图 1．图的基本概念、名词术语； 2．图的邻接矩阵存储方法和邻接表(含逆邻接表存储方法的构造原理及特点； 3．图的深度优先搜索与广度优先搜索； 4．最小(代价生成树、最短路径、AOV网与拓扑排序以及AOE网与关键路径的基本概念与求解过程。六、文件及查找 1．顺序查找法以及平均查找长度(ASL的计算； 2．折半查找法以及平均查找长度(ASL的计算，包括查找过程对应的"判定树"的构造； 3．B-树和B+树的基本概念，B-树的插入与查找； 4．散列(Hash表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。七、内排序 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．便于按行处理矩阵元素

湘西自治州事业单位考试公基真题-答案(精选)

湘西事业单位考试 公共基础知识 一、判断题 1.√.【解析】本题考查政治常识。发展是当代世界的主题，也是当代中国的主题。社会发展重在提高社会和谐和文明程度。从全人类的角度看，发展是世界范围内实现现代化的过程，发展问题实质上就是现代化问题。科学发展观，第一要务是发展，核心是以人为本，基本要求是全面协调可持续发展，根本方法是统筹兼顾。科学发展观是全面建设小康社会和实现社会主义现代化的根本指针，统领经济社会发展的全局。所以现代化的社会发展主要是指科学发展。因此，本题说法正确。 2.×.【解析】本题考查公文。公文的发送既可以有一个主送机关，也可以有多个主送机关。如请示必须只有一个主送机关。通知则可以有多个主送机关。因此，本题说法错误。 3.×.【解析】本题考查法律常识。行政部门有权无责，容易导致滥用公权。因此，本题说法错误。 4 .×.【解析】本题考查政治常识。我国经济体制改革的基本目标是把高度集中的计划经济体制改革成为社会主义市场经济体制，其实质是社会主义制度的自我完善和发展。因此，本题说法错误。 5.√.【解析】本题考查管理常识。新型事业单位管理体制，就是要按照政事分开原则，让事业单位与政府部门脱钩，取消行政隶属关系，建立法人治理结构，让事业单位拥有自主权和灵活性，从党政机关的附属物，转变成为社会发展主体———独立的事业法人，形成事业法人治理结构，其实质是政府与事业单位的关系问题。因此，本题说法正确。 6.√.【解析】本题考查法律常识。法是以国家强制力为后盾，通过法律程序保证实现的社会规范。这是法的一个重要特征。因此，本题说法正确。 7.×.【解析】本题考查政治常识。我国人民代表大会制度的核心是国家的一切权力属于人民。因此，本题说法错误。 二、单选题 1.B.【解析】本题考查法律常识。根据《公司法》第27条规定，有限责任公司的股东可以用货币出资，也可以用实物、知识产权、土地使用权等可以用货币估价并可以依法转让的非货币财产作价

数据结构考试题库

绪论 一、填空题 1.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系

4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。

《数据结构》课程考试大纲

03 《数据结构》考试大纲 主要参考教材：严蔚敏、吴伟民编著，《数据结构（C语言版）》，清华大学出版社 谭国律等编著《数据结构》，浙江大学出版社。 总体要求： “数据结构”是一门专业技术基础课。目的就是要培养他们的数据抽象能力，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及实现应用的相应算法，并掌握分析算法的时间和空间复杂度的技术。 考生在复习时，重点掌握基本概念、基本算法。考题以基本内容为主，题目以基础知识题为主，各章较难内容、较偏内容不考。课本所有加“*”号章节不考，第8章动态存储管理不考。外部排序，文件部分不考。 各章考试内容及要求： 一、绪论：熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之 间的关系；了解抽象数据类型的定义、表示和实现方法；熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式；理解算法五个要素的确切含义；掌握计算语句频度和估算算法时间复杂度的方法。 二、线性表：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线 性表的两类存储结构（顺序存储和链式存储）上实现基本操作；一元多项式的抽象数据类型定义、表示及加法的实现。

三、栈和队列：栈和队列的结构特性；在两种存储结构上如何实现栈和队列的基本操作和栈 和队列在程序设计中的应用。（离散事件模拟不考） 四、串：串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆 分配存储结构；串的各种基本操作的实现及应用；串的朴素模式匹配算法。 五、数组：数组的类型定义和表示方法；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实 现；（广义表不考）。 六、树和二叉树：二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法 的各种描述形式；树和森林的定义、存储结构、树和森林与二叉树的转换、遍历；树的多种应用；本章是该课程的重点内容之一。 七、图：图的定义和术语；图的邻接矩阵存储结构、邻接表存储结构：图的两种遍历策略： 深度优先搜索和广度优先搜索；图的最小生成树prim算法、Kruskal 算法；拓扑排序算法；单源最短路径问题的Dijstra 算法。 八、查找：讨论查找表（包括静态查找表和动态查找表）的各种实现方法：顺序表、有序表、 树表和哈希表；关于衡量查找表的主要操作——查找的查找效率的平均查找长度的讨论。（静态树表、平衡二叉树、B树不考）

《数据结构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. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。

2020年事业单位考试公共基础知识试题库及答案

2020年事业单位考试公共基础知识试题库及答案 1.所有的社会问题都是源于“文化价值上的冲突”这是社会学中（）理论流派的观点。 A: 文明冲突论B: 社会解体论 C: 文化失调论D: 价值冲突论 答案: D 2.加强和改进党的作风建设，核心问题是：（） A: 保持党和人民群众的血肉联系B: 提高党员的思想水平和学习能力 C: 发挥党的纪律检查委员会的作用D: 培养年轻干部 答案: A 3.在社会生活中，上层建筑对于社会发展作用的性质取决于：（） A: 国家政权的阶级属性B: 它所服务的经济基础的性质 C: 社会意识形态的性质D: 社会生产力的性质 答案: B 4.社会变迁是指：（） A: 社会由无序向有序、由低级向高级的演进 B: 社会结构的变化与调整。

C: 表示一切社会现象，特别是社会结构发生变化的动态过程及其结果的范畴D: 社会渐进性的平缓变化过程 答案: C 5税收是国家为实现其职能依法无偿取得财产收入的基本形式，其具有： A.公益性、无偿性、固定性 B.公益性、强制性、固定性 C.公益性、无偿性、强制性 D.强制性、无偿性、固定性 答案：D . 6.下列机构中，有权依法制定地方政府规章的是： A.某直辖市人民代表大会 B.某自治区人民代表大会常务委员会 C.某省人民政府所在地的市人民政府 D.某省人民政府的工作部门 答案：C 试题7：江泽民同志提出的“三个代表”的具体内容是：（） A: 中国共产党要代表中国先进生产力的发展要求B: 中国共产党要代表中国先进文化的前进方向 C: 中国共产党要代表中国最广大人民的根本利益D: 中国共产党要切实代表工人阶级的根本利益

数据结构考试题库含答案

数据结构习题集含答案 目录

选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性

7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0;

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

模拟试卷一 一、单选题（每题 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)，下面哪一个序列是从上述序列出发建 堆的结果?( )

数据结构试题及答案

第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i

2018西安邮电大学初试考试大纲—826数据结构

西安邮电大学硕士研究生招生考试大纲 科目代码：826 科目名称：《数据结构》 一、课程性质和任务 数据结构是计算机各专业的专业基础课。它是操作系统、数据库、编译原理等所有软件专业基础课和专业课的重要基础；它还是进行程序设计，尤其是进行高水平的应用程序和系统程序必不可少的基础。通过本课程的学习，使学生掌握数据组织、存储和运算的基本原理和方法，培养学生对各类数据结构和相关算法的分析和设计的能力，使学生能够编写出正确、清晰和较高质量的算法和程序。 二、课程教学内容和要求 第一章数据结构和算法 1.了解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。 2.了解数据结构的发展和地位。 3.了解各种算法描述方法和算法设计的基本要求。 4.掌握对算法的评价标准和算法效率的度量方法。 第二章线性表 1.理解线性表的概念、定义、逻辑结构和存储结构。 2.熟练掌握线性表的顺序结构及其各种基本运算。 3.熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本运算。 4.理解链表的应用——稀疏多项式存储和运算。 第三章栈和队列 1.掌握栈的定义、表示、实现和应用。 2.掌握递归的概念和递归的实现过程。 3.掌握队列的定义以及顺序（循环队列）和链式存储结构的实现。 第四章串 1.了解串的基本概念及顺序和链式存储结构。 2.掌握串的各种基本运算。

3.了解串的模式匹配算法。 第五章数组和广义表 1.掌握数组的顺序存储结构。 2.理解稀疏数组的概念和压缩存储的方法。 3.理解稀疏矩阵的三元组存储结构和基本运算。 4.了解稀疏矩阵的十字链表存储结构。 5.理解广义表的基本概念，掌握广义表的存储结构。 第六章树 1.理解树的基本概念及其存储结构。 2.熟练掌握二叉树的定义、性质以及各种存储结构和遍历算法。 3.掌握线索二叉树的概念、存储结构及线索化算法。 4.掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法。 5.掌握哈夫曼树的概念、存储结构和应用。 第七章图 1.理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构。 2.了解十字链表，邻接多重表等存储结构。 3.熟练掌握图的深度优先和广度优先遍历算法。 4.理解图的连通性、最小生成树的概念。 5.掌握求最小生成树算法。 6.理解有向无环图的概念，掌握拓扑排序和关键路径算法。 7.理解带权最短路径的概念，掌握求最短路径的算法。 第八章查找 1.理解查找的概念及其效率的评价方法。 2.理解静态查找表的概念，熟练掌握顺序、折半和分块查找算法。 3.理解动态查找表和二叉排序树的概念。 4.了解平衡二叉树的概念。 5.理解哈希表的含义，掌握哈希函数的构造和处理冲突的基本方法。第九章内部排序 1.掌握插入类排序的算法：直接插入排序、希尔排序。

数据结构模拟试卷(含答案)

数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。

A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆

武汉市事业单位考试《公共基础知识》真题(完整版)

武汉市事业单位考试试题完整版 《公共基础知识》（教育类） （满分：100分时限：90分钟） 一、是非题（判断下列各题正误，正确的请在答题卡上按对应题号把Ａ涂黑，错误的把Ｂ涂黑。每题0.6分，共12分） 1．“安而不忘危，存而不忘亡，治而不忘乱”这句话启示我们矛盾的主要方面决定事物的性质。（） 2.唯物主义真理观和唯心主义真理观的区别是是否承认真理的客观性。（） 3.人在心情愉快时会感到“光阴似箭”，心情抑郁时会感到“度日如年”这表明时间的具体特性是可变的。（） 4.唯物辩证法和形而上学斗争的焦点集中在是否承认事物是永恒发展的。（） 5.货币流通规律的基本要求是货币发行量应相当于商品流通中对金属货币的需要量。（） 6.相对剩余价值的获得是企业劳动生产率高于部门平均劳动生产率的结果。（） 7.个别的企业工人的剩余劳动是超额剩余价值的源泉。（） 8.根据《刑法》规定，醉酒的人犯罪不负刑事责任。（） 9.在《民法》中，把年满16周岁未满18周岁并以自己的劳动收入为主要生活来源且精神正常的自然人视为完全民事行为能力人。（） 10.行政处罚是行政主体依法对违反行政法律规范的管理相对人的惩罚。（） 11.行政诉讼的被告只能是行政机关。（） 12.上级人民法院领导下级人民法院的审判工作。（） 13.代理产生的法律后果由代理人承担。（） 14.所有权的四项权能是占有、使用、收益和处分。（） 15.行政权力是以强制力作为后盾，具有某种强制性。（） 16.行政价值是对行政管理系统所追求目标的应然性概括。（） 17.在议论中以充分的论据从正面证明自己论点正确的方法称之为申论。（） 18.文章主题是一种“观念”，是人们对现实生活的理性认识。（） 19.条例、规定、办法的撰写，一般以章节、条款的形式安排表达次序。（） 20.廉洁奉公这一道德规范，要求公务员做到艰苦朴素。（） 二、单项选择题(下列各题的备选答案中，只有一项是符合题意的，请将所选答案的字母代号填涂在答题卡上。每题0.8分，共48分) 21.社会建设与人民幸福安康息息相关。党的十七大报告提出，要加快推进以改善民生为重点的社会建设。下列各项不属于社会建设范畴的是（）。 A.在学校建立贫困生活资助体系