福建师范大学数据结构期末考试试题

“数据结构”期末考试试题

一、单选题(每小题2分，共12分)

1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL；

D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边

C.n(n—1)／2条有向边 D.n(n一1)条有向边

3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n)

C.O(1Ogzn) D.O(n2)

4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48

C． 72 D． 53

5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

A.整形 B.引用型

一、名词解释

1、瓦格纳法则

答：随着人均收入的提高，财政支出占GDP的比重也相应提高，即随着人均收入的提高，财政支出的提高率高于GDP的增长率。

2、财政补贴

答：是政府为了某种特定需要而将一部分财政资金无偿的发给居民、企业及其他受益者的支出，政府进行财政补贴，实质上是把纳税人的一部分收入无偿

转移给补贴领受者，是一种转移性支出，会引起国民收入的再分配。

3、社会保障

答：政府以法律的形式确定满足社会成员各种社会保障需求的社会保障措施。此时的社会保障被称为社会保障制度。它不仅具有规范性，而且保障范围也十

分广泛。这种社会保障是于社会化和专业化相适应的。综合比较不同国家的社

会保障制度，它们大体包括社会保险和社会救济两部分

三、简答题

1．请简述公共投资的特点。

答：（1）公益性。公共投资追求社会效益的最大化，而不以经济效益为目标。基

础设施和公益性设施只能或主要靠政府来集中提供，以满足社会的共同需要。（2）无偿性。公共投资的使用一般是无偿的，无法通过计价收费的方式来补偿，伙食只能得

到部分补偿。政府投资提高了居民的生活质量，企业和居民则无偿地向政府上缴税款，然后政府再继续用于公共投资，从而间接地形成公共投资的循环。(3)政策性。公共投资必须考虑国家产业政策。因其投资主

2005年－2006学年第二学期“数据结构”考试试题（A）

姓名学号(序号)_ 答案隐藏班号

要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共20分）

1．数据的运算a 。

A.效率与采用何种存储结构有关

B.是根据存储结构来定义的

C.有算术运算和关系运算两大类

D.必须用程序设计语言来描述

答：A。

2. 链表不具备的特点是 a 。

A.可随机访问任一结点

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

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

D.所需空间与其长度成正比

答：参见本节要点3。本题答案为：A。

3. 在顺序表中删除一个元素的时间复杂度为 c 。

A.O(1)

B.O(log2n)

C.O(n)

D.O(n2)

答：C。

4．以下线性表的存储结构中具有随机存取功能的是 d 。

A. 不带头结点的单链表

B. 带头结点的单链表

C. 循环双链表

D. 顺序表

解 D。

5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。

A.edcba

B.decba

C.dceab

D.abcde

答：C。

6. 循环队列qu的队空条件是 d 。

A. (qu.rear+1)%Max

2005年－2006学年第二学期“数据结构”考试试题（A）

姓名学号(序号)_ 答案隐藏班号

要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共20分）

1．数据的运算a 。

A.效率与采用何种存储结构有关

B.是根据存储结构来定义的

C.有算术运算和关系运算两大类

D.必须用程序设计语言来描述

答：A。

2. 链表不具备的特点是 a 。

A.可随机访问任一结点

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

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

D.所需空间与其长度成正比

答：参见本节要点3。本题答案为：A。

3. 在顺序表中删除一个元素的时间复杂度为 c 。

A.O(1)

B.O(log2n)

C.O(n)

D.O(n2)

答：C。

4．以下线性表的存储结构中具有随机存取功能的是 d 。

A. 不带头结点的单链表

B. 带头结点的单链表

C. 循环双链表

D. 顺序表

解 D。

5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。

A.edcba

B.decba

C.dceab

D.abcde

答：C。

6. 循环队列qu的队空条件是 d 。

A. (qu.rear+1)%Max

第一部分 选择题(30分)

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (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是（ ）。

(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的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (C) p=p->next->next

(B) p=p->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3

第一部分 选择题(30分)

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (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是（ ）。

(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的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (C) p=p->next->next

(B) p=p->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3

北京邮电大学数据结构期末考试试题

北京邮电大学数据结构期末考试试题(A卷)

一．单项选择题（2分/题）

1．一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。

A.23415 B.54132 C.31245 D.14253

2． 设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。

A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n

3． 二叉树在线索化后，仍不能有效求解的问题是（D）。

A.先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继

4． 求最短路径的FLOYD算法的时间复杂度为（D）。

A.O(n) B.O(n+e) C.O(n2) D.O(n3)

5． 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B）。

A.0 B.1 C.2 D.不确定

6． 数组A[1..5,1.

一、 选择题 A、94,32,40,90,80,46,21,69 1.在逻辑上可以把数据结构分A.P->NEXT=Q->NEXT;FREE(Q); B、32,40,21,46,69,94,90,80 成（ A） B.Q->NEXT=P; FREE(Q); C 21,32,46,40,80,69,90,94 A.线性结构和非线性结构 D、90,69,80,46,21,32,94,40 B.动态结构和静态结构 C.Q->NEXT=P->NEXT;FREE(Q); 21.若用冒泡排序对关键字序C.紧凑结构和非紧凑结构 D.P->NEXT=S;S->NEXT=P; 列（18,16,14,12,10,8）进行从D.内部结构和外部结构 2. 单链表中各结点之间的地址（C） A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对 3.在一个长度为n的顺序表中向第i个元素（0

一、 选择题 A、94,32,40,90,80,46,21,69 1.在逻辑上可以把数据结构分A.P->NEXT=Q->NEXT;FREE(Q); B、32,40,21,46,69,94,90,80 成（ A） B.Q->NEXT=P; FREE(Q); C 21,32,46,40,80,69,90,94 A.线性结构和非线性结构 D、90,69,80,46,21,32,94,40 B.动态结构和静态结构 C.Q->NEXT=P->NEXT;FREE(Q); 21.若用冒泡排序对关键字序C.紧凑结构和非紧凑结构 D.P->NEXT=S;S->NEXT=P; 列（18,16,14,12,10,8）进行从D.内部结构和外部结构 2. 单链表中各结点之间的地址（C） A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对 3.在一个长度为n的顺序表中向第i个元素（0

安徽大学2014-2015学年第一学期《数据结构》期末考试试卷（A卷）

（含参考答案）

一、 单项选择题（本大题共15小题，第小题2分，共30分）在每小题列出的四个选项中只有一

个符合题目要求，请将其代码填在题后的括号内。错选或未选均无分。

1. 算法必须具备输入、输出和 [ C ]

A. 计算方法 B. 排序方法 C．解决问题的有限运算步骤 D. 程序设计方法

2. 有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是 [ A ]

A. 访问第i个节点（1≤i≤n）

B. 在第i个节点后插入一个新节点（1≤i≤n） C. 删除第i个节点（1≤i≤n） D. 将n个节点从小到大排序

3．单链表的存储密度 [ C ]

A．大于1 B. 等于1 C．小于1 D. 不能确定

4. 循环队列SQ的存储空间是数组d[m]，队头、队尾指针分别是front和rear，则执行出队后其头指针front值是