西北师范大学数据结构期末考试试题

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

一、单选题(每小题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.引用型

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值是

这是我整理的关于c语言期末考试的重要笔记,主要是代码部分。

C语言复习整理

1、 素数：求1——200的所有素数。

#include<stdio.h>

#include<math.h>

void main()

{

int i,j,leap;

for(i=2;i<=100;i++)

{

leap=1;

for(j=2;j<=sqrt(i);j++)

if(i%j==0)

leap=0;

if(leap==1)

printf("%4d",i);

}

printf("\n");

}

2、 输入一个年份，判断是否为闰年。

#include<stdio.h>

void main()

{

int year;

printf("请输入年份:");scanf("%d",&year);

if((year%4==0&&year%100!=0)||year%400==0)

printf("%d年是闰年.\n",year);

}

3、 画出各种三角形图案。（这是用循环嵌套完成的，也可以用二维数组来输出更加直接简

单，但是耗费系统资源较多。）

#include