数据结构（C语言篇）―习题与解析（修订版）
清华大学出版社
一、绪论
选择题
1.数据结构是一门研究非数值计算的程序设计问题计算机的以及它们之间的和运算等的学科。
1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像
2 A.结构 B.关系 C.运算 D.算法
2.数据结构被形式地定义为 (K, R)，其中K是的有限集，R是K 上的有限集。
1 A.算法 B.数据元素 C.数据操作 D.逻辑结构
2 A.操作 B.映像 C.存储 D.关系
3.在数据结构中，从逻辑上可以把数据结构分成。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
4.线性结构的顺序存储结构是一种 A 的存储结构，线性表的链式存储结构是一种 B 的存储结构。
A.随机存取
B.顺序存取
C.索引存取
D.散列存取
5.算法分析的目的是 C ，算法分析的两个主要方面是AB 。
1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进
D.分析算法的易懂性和文档性
2 A.空间复杂度和时间复杂度 B.正确性和简单性
C.可读性和文档性
D.数据复杂性和程序复杂性
6.计算机算法指的是 C ，它必须具备输入、输出和 B 等5个特性。
1 A.计算方法 B.排序方法 C.解决问题的有限运算序列
D.调度方法
2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性
C.确定性、有穷性和稳定性
D.易读性、稳定性和安全性
7.线性表的逻辑顺序与存储顺序总是一致的，这种说法 B 。
A.正确
B.不正确
8线性表若采用链式存储结构时，要求内存中可用存储单元的地址D 。
A.必须连续的
B.部分地址必须连续的
C.一定是不续的D 连续不连续都可以
9.以下的叙述中，正确的是 B 。
A.线性表的存储结构优于链式存储结构
B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进后出
D.队列的操作方式是
先进先出
10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法 B 。
A.正确
B.不正确
填空题
1.数据逻辑结构包括三种类型线性结构、树形结构和图形结构，树形结构和图形结构合称为非线性结构。
2.在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。
3.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续可以任意多个。
4.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。
5.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
6.算法的五个重要特性是有穷性、确定性、可行性、输入、输出。
7.下面程序段的时间复杂度是O（m*n）。
for( i = 0; i < n; i++)
for( j = 0; j < m; j++)
A[i][j] = 0;
8.下面程序段的时间复杂度是O（n）。
i = s = 0;
while ( s < n)
{
i ++; /* i = i +1*/
s += i; /* s = s + i*/
}
9.下面程序段的时间复杂度是O（n2）。
s = 0;
for( i = 0; i < n; i++)
for( j = 0; j < n; j++)
s += B[i][j];
sum = s;
10.下面程序段的时间复杂度是O（log3n）。
i = 1;
while ( i <= n )
i = i * 3;
二、线性表
单项选择题
1.一个向量第一个元素的存储地址是100，每个元素的长度为2，则
第5个元素的地址是 B 。
2.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是
C 。
3.若一个栈的入栈序列是1、2、3、…、n，其输出序列为p1、p2、p3、…、p n，若p1=n，则p i为C。
A. i
B. n = i
C. n - i +1
D.不确定
4.栈结构通常采用的两种存储结构是A。
A.线性存储结构和链表存储结构
B.散列方式和索引方式
C.链表存储结构和数组
D.线性存储结构和非线性存储结构
5.判断一个栈ST (最多元素为m) 为空的条件是B。
>top!=0 B. ST->top==0 C. ST->top!= m D. ST->top== m
6.判断一个栈ST (最多元素为m) 为满栈的条件是D。
>top!=0 B. ST->top==0 C. ST->top!= m-1 D. ST->top== m-1
7.栈的特点是 B ，队列的特点是 A 。
A.先进先出，后进后出
B.先进后出，后进先出
8.一个队列的入队序列是1、2、3、4，则队列输出序列是 B 。
、3、2、1 、2、3、4、4、3、2 、2、4、1
9.判断一个队列QU (最多元素为m) 为空的条件是 C 。
A. QU->rear－QU->front == m
B. QU->rear－QU->front －1 == m
C. QU->front == QU->rear
D. QU->front－QU->rear + 1
10.判断一个队列QU (最多元素为m) 为满队列的条件是
A 。
A. QU->rear－QU->front == m
B. QU->rear－QU->front －1 == m
C. QU->front == QU->rear
D. QU->front－QU->rear + 1
11.判断一个循环队列QU (最多元素为m) 为空的条件是。
A. QU->front == QU->rear
B. QU->front != QU->rear
C. QU->front == (QU->rear + 1) %m
D. QU->front != (QU->rear + 1) %m
12.判断一个循环队列QU (最多元素为m) 为满队列的条件是。
A. QU->front == QU->rear
B. QU->front != QU->rear
C. QU->front == (QU->rear + 1) %m
D. QU->front !=
(QU->rear + 1) %m
13循环队列用数组A[0, m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。
A.(rear－front + m) %m
B. rear－front + 1
C. rear －front－1
D. rear－front
14.栈和队列的共同点是。
A.都是先进后出
B.都是先进先出
C.只允许在端点处插入、删除元素
D.没有共同点
填空题
1.向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入元素和删除元素。
2.在一个长度为n的向量中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动个元素。
3.在一个长度为n的向量中的删除第i个元素(1≤i≤n)时，需要向前移动个元素。
4.向栈中压入元素的操作是。
5.对栈进行退栈时的操作是。
6.在一个循环队列中，队首指针指向队首元素的。
7.从循环队列中删除一个元素时，其操作是。
8.在具有n个单元的循环队列中，队满时共有个元素的。
9.一个栈的输入序列是12345，则栈的输出序列43512是。
10.一个栈的输入序列是12345，则栈的输出序列12345是。
三、链表
单项选择题
1.不带头结点的单链表head为空的判定条件是。
==NULL >nxt==NULL >next==head !=NULL
2.带头结点的单链表head为空的判定条件是。
==NULL >nxt==NULL >next==head !=NULL
3.非空的循环单链表head的尾结点（由p所指向）满足。
>next==NULL ==NULL >next==head ==head
4.在循环双链表的p所指结点之后插入s所指结点的操作是。
A.
p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B.
p->right=s;p->right->left=s;s->left=p;s->right=p->right;
C.
s->left=p;s->right=p->right;p->right=s;p->right->left=s;
D. s->left=p;s->right=p->right;
p->right->left=s;p->right=s;
5.在一个单链表中，已知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;
6.在一个单链表中，已知p所指结点不是最后结点，在p之后插入s
所指结点，则执行。
A. s->next = p; p->next=s;
B. s->next = p->next; p->next = s;
C. s->next = p->next; p = s;
D. p->next = s; s->next = p;
7.在一个单链表中，若删除p所指结点的后续结点，则执行。
A. p->next = p->next->next;
B. p = p->next; p->next=p->next->next;
C. p->next = p->next;
D. p =p->next ->next;
9.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较个结点。
A. n
B. n/2
C. (n-1)/2
D. (n+1)/2
10.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序
的时间复杂度是。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
11.给定有n个元素的向量，建立一个有序单链表的时间复杂度是。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
12.向一个栈顶指针为HS的链栈中插入s所指结点，则执行。
A. HS->next = s;
B. s->next = HS->next; HS->next = s;
C. s->next = HS; HS = s;
D. s->next = HS; HS = HS->next;
13.从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结
点的值，则执行。
A. x = HS; HS = HS->next;
B. x = HS->data;
C. HS = HS->next; x = HS->data;
D. x = HS->data; HS = HS->next;
14.在一个链队中，假设f和r分别为队首和队尾指针，插入s所指
结点，则执行。
A. f->next = s; f = s;
B. r->next = s; r = s;
C. s->next = r; r = s;
D. s->next = f; f = s;
15. 在一个链队中，假设f和r分别为队首和队尾指针，删除一个结
点，则执行。
A. r = f->next;
B. r = r->next;
C. f = f->next;
D. f = r->next;
填空题
1.单链表是的链接存储表示。
2.可以使用表示树形结构。
3.在双链表中，每个结点有两个指针域，一个指向，另一个指向。
4. 在一个单链表中，p所指结点之前插入s所指向结点，可执行如
下操作：
（1）s->next = ；
（2）p->next = s；
（3）t = p->data；
（4）p->data = ；
（5）s->data = ；
5.在一单链表中，删除p所指结点时，应执行以下操作：
（1）q = p->next；
（2）p->data = p->next->data；
（3）p->next = ；
（4）free (q)；
6.带头结点的单链表head为空的条件是。
7.在一个单链表中，p所指结点之后插入s所指向结点，应执行
s->next = 和
p->next = 的操作。
8.非空的循环单链表head的尾结点（由p所指向），满足。
9.在栈顶指针为HS的链栈中，判定栈空的条件是。
10. 在栈顶指针为HS的链栈中，计算该链栈中结点个数的函数是。
11.在HQ的链队中，判定只有一个结点的条件是。
12.在HQ的链队中，计算该栈链中结点个数的函数是。
四、串
单项选择题
1.空串与空格串是相同的，这种说法。
A.正确
B.不正确
2.串是一种特殊的线性表，其特殊性体现在。
A.可以顺序存储
B.数据元素是一个字符
C.可以链接存储
D.数据元素可以是多个字符
3.设两个字符串p和q，求q在p中首次出现的位置的运算称
作。
A.连接
B.模式匹配
C.求子串
D.求串长
4.设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x, y) 返回x与y串的连接串，函数subs (s, i, j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len (s) 返回串s的长度，则
con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的结果串是。
A. BCDEF
B. BCDEFG
C. BCPQRST
D. BCDEFEF
填空题
1.串的两种最基本的存储方式是。
2.两个串相等的充分必要条件是。
3.空串是，其长度等于。
4.空格串是，其长度等于。
5.设s = ‘I AM A TEACHER’，其长度是。
6.设s1 = ‘GOOD’，s2 = ‘’，s3 = ‘BYE!’，则s1、s2和s3连接后的结果是。
五、数组与稀疏矩阵
单项选择题
1.常对数组进行的两种基本操作是。
A.建立与删除
B.索引和修改
C.查找和修改
D.查找与索引
2.二维数组M的成员是6个字符（每个字符占一个存储单元）组成的
串，行下标i的范围从
0到8，列下标j的范围从1到10，则存放M至少需要 1 个字节；M的第8列和第5
行共占 2 个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先
方式存储时的 3 元素的起始地址一致。
1
2
3 [8][5] [3][10] [5][8] [0][9]
3.二维数组M的成员是4个字符（每个字符占一个存储单元）组成的
串，行下标i的范围从
0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元
素的元素的起始地址一致。
[2][4] [3][4] [3][5] [4][4]
4.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下
标j从1到10，从首地
址SA开始连续存放在存储器内，存放该数组至少需要的单元素是。
A. 80
B. 120
C. 240
D. 270
5.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下
标j从1到10，从首地
址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为。
A. SA+141
B. SA+144
C. SA+222
D.
SA+225
6.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下
标j从1到10，从首地
址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为。
A. SA+141
B. SA+180
C. SA+222
D. SA+225
7.稀疏矩阵一般的压缩存储方法有两种，即。
A. 二维数组和三维数组
B. 三元组与散列
C. 三元组与十字链表
D. 散列和十字链表
8.若用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点。
A. 正确
B. 不正确
9.设矩阵A是一个对称矩阵，为节省存储，将其下三角部分按行序存放在一信数组B[1, n(n-1)/2]中，对下三角部分中任一元素a ij (i≥j)，在一组数组B的下标位置k的值是。
A. i (i-1)/2+j-1
B. i (i-1)/2+j
C. i (i+1)/2+j-1
D. i (i+1)/2+j
填空题
1.已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是。
2.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储
单元，并且A[0][0]的存储地址是200，则A[6][10]的地址是
。
3.二维数组A[10..20][5..20]采用行序为主方式存储，每个元素占4
个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址
是 。
4.有一个10阶对称矩阵A ，采用压缩存储方式（以行为主存储，且
LOC(A[0][0])=1），则
A[8][5]的地址是 。
5.设n 行n 列的下三角矩阵A 已压缩到一维数组S[1..n*(n+1)/2]中，
若按行序为主存储，则
A[i][j]对应的S 中的存储位置是 。
6.一个稀疏矩阵如图所示，则对应的三元数组表示为 。
????????????-00005100000302
00 八、树形结构
单项选择题
1.如图所示的4棵二叉树中， 不是完全二叉树。
3.在线索化二叉树中，t 所指结点没有左子树的充要条件是 。
>left == NULL >ltag == 1 >ltag == 1且t->left == NULL
D.以上都不对
4.二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线
索，这种说法。A.正确
B.错误
5.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前
面，这种说法。
A.正确
B.错误
6.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，
这种说法。
A.正确
B.错误
7.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树
中所包含的结点数至少
为。
A. 2h
B. 2h-1
C. 2h +1
D. h +1
8.如图所示二叉树的中序遍历序列是。
A. abcdgef
B. dfebagc
C. dbaefcg
D. defbagc
9.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，
前序遍历序列是。
A. acbed
B. decab
C. deabc
D. cedba
10.如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就
是T2中结点的。
A. 前序
B. 中序
C. 后序
D. 层次序
11.如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就
是T2中结点的。
A. 前序
B. 中序
C. 后序
D. 层次序
12某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访
问顺序是dgbaechf，则其后序遍历结点访问顺序是。
A. bdgcefha
B. gdbecfha
C. bdgaechf
D. gdbehfca
13.二叉树为二叉排序树的充分必要条件是任一结点的值均大于其左孩子的值、小于其右孩子的值，这种说法。
A. 正确
B. 错误
14.按照二叉树的定义，具有3个结点的二叉树有种。
A. 3
B. 4
C. 5
D. 6
15.如图所示二叉树的中序遍历序列是。
A. abdgcefh
B. dgbaechf
C. gdbehfca
D. abcdefgh
16.树的基本遍历策略可分为先根遍历和后根遍历；二叉树基本遍历
策略可分为先序遍历、
中序遍历和后序遍历。这时，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论
是正确的。
A. 树的先根遍历序列与二叉树的先序遍历序列相同
B. 树的后根遍历序列与二叉树的后序遍历序列相同
C. 树的先根遍历序列与二叉树的中序遍历序列相同
D. 以上都不对
17.深度为5的二叉树至多有个结点。
A. 16
B. 32
C. 31
D. 10
18.在一非空二叉树的中序遍历序列中，根结点的右边。
A. 只有右子树上的所有结点
B. 只有右子树上的部分结点
C. 只有左子树上的所有结点
D. 只有左子树上的部分结点
19.树最适合用来表示。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
20任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序。
A. 不发生改变
B. 发生改变
C. 不能确定
D. 以上都不对
21.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳
方案是二叉树采用
存储结构。
A. 二叉链表
B. 广义表存储结构
C. 三叉链表
D. 顺序存储结构
22.对于一个满二叉树，m个树叶，n个结点，深度为h，则。
A. n = h + m
B. h + m = 2n
C. m = h-1
D. n = 2 h -1
23.如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后
序。
A. uwvts
B. vwuts
C. wuvts
D. wutsv
25.如图所示的T2是由有序树T1转换而来的二叉树，那么树T1有个叶结点。
A. 4
B. 5
C. 6
D. 7
26.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的
条件是。
A. n在m右方
B. n是m祖先
C. n在m左方
D. n是m子孙
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 .没有共同点
数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 数据结构考试题库 绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。 ？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理，用心做精品2 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）时，需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理，用心做精品3 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head！=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表：表中各结点都没有直接前趋和直接后继。 在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中，使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表 栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234，则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by . a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search 第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next 数据结构考试及答案（） 作者: 日期: 2 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D） A 必须是连续的B部分地址必须是连续的 C 一定是不连续的D可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 （D ）。 An B n/2 C （n-1）/2 D （n+1）/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D ）o A s—link = p—link ；p—link = s； B p—link = s; s—link = q; C p—link = s—link ；s—link = p； D q—link = s; s—link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（C ）方法最好。 A 起泡排序 B 堆排序C锦标赛排序 D 快速 排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（B ）o A 求子串B模式匹配C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j] 占用3个存储字，行下标i从1到8, 列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈B队列C循环队列D优先队列 9、一个队列的进队列顺序是1,2, 3, 4 ，则出队列顺序为（C ）。 10、在循环队列中用数组A[0.. m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A （ front - rear + 1） % m B （rear - front + 1） %m C （ front - rear + m） % m D （ rear - front + n） % m 11、一个数组元素a[i]与（A ）的表示等价。 A * （a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数 A指针 B 引用C值 D 变量 13、下面程序段的时间复杂度为（C) for (i nt i=0;i 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 2012年数据结构期末考试题及答案 一、选择题 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．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 数据结构习题 习题一 一、选择题 1、算法分析的两个主要方面是：（） A．正确性和简明性B．时间复杂度和空间复杂度 C．数据复杂性和程序复杂性D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3、计算机算法具备输入、输出和（）等5个特性： A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性 4、算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系， 图形结构中元素之间存在的关系。 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。 4、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。 5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j 绪论 一、填空题 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（++）。 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。 for(i=n-1；i>=0；i--) for(j=0；j数据结构考试题库
数据结构课后习题及解析第二章
数据结构期末考试试题及答案
数据结构题库教材
《数据结构》期末考试题及答案
数据结构例题解析(1)
数据结构相关题库及答案
数据结构考试及答案()
数据结构第一章课后习题与答案
2015年数据结构期末考试题及答案
数据结构题库汇总
数据结构考试题库
数据结构考试题库含参考答案
数据结构期末考试试题及答案
算法与数据结构题库与答案
数据结构期末考试试题及答案
相关主题
文本预览