第1章概论
练习题
一、单项选择题
1．在数据结构中，从逻辑上可以把数据结构分为（B）A．紧凑结构和非紧凑结构B．线性结构和非线性结构
C．内部结构和外部结构D．动态结构和静态结构2．若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（D）A．顺序存储结构B．链式存储结构
C．索引存储结构D．散列存储结构
3．算法分析的两个主要方面是（B）A．正确性和简明性B．时间复杂性和空间复杂性
C．可读性和可维护性D．数据复杂性和程序复杂性4．线性表采用链式存储结构时，要求内存中可用存储单元地址（A）A．不一定连续的B．部分地址必须是连续的
C．必须是连续的D．一定是不连续的
5．算法指的是（C）A．计算机程序B．解决问题的计算方法
C．解决问题的有限运算序列D．排序算法
二、填空题
6．数据结构一般包括逻辑结构、存储结构和数据运算三个方面的内容．
7．数据的逻辑结构可分为线性结构、非线性结构两大类．
8．数据的存储结构（物理结构）一般可以用顺序存储结构、链式存储结构、索引存储结构及散列存储结构等四种存储方法表示．
9．在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑执行算法所需要的时间、执行算法所需要的存储空间及算法应易于理解、易于编程、易于调试等三点。
10．设有一批数据元素，为了最快地存取某元素，宜用顺序结构存储，为了方便的插入一个元素，宜用链式结构存储．
三、应用题
设n为正整数，利用大“O”记号，写出下列各程序段的时间复杂度．
11．for (i = 1; i <= n; i++){
y = y + 1;
for (j = 1; j <= 2 * n; j++)
x = x + 1;
}
分析：语句“y = y + 1;”执行n次，语句“x = x + 1;”各执行2
2n次，故该程序段的时间复杂度为O(2n)．12．s = 0;
while (n >= (s + 1) * (s + 1))
s = s + 1;
分析：语句“s = s + 1;．
13．x = 1;
sum = 0;
for (i = 0; i <= n; i++){
x = x * i;
sum = sum + x;
}
分析：语句“x = x * i”和“sum = sum + x;”各执行n次，故该程序段的时间复杂度为O(n)．
14．for (i = 1; i <= n; i++)
if (3 * i <=n)
for (j = 3 * i; j <= n; j++){
x++;
y = 3 * x + 2;
}
分析：语句“x++”和“y = 3 * x + 2;”各执行1(1)
n n-次，故该程序段的时间复杂度为O(2n)．
6
15．for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++){
x = x + 1;
}
分析：语句“x = x + 1;”执行1(1)
n n+次，故该程序段的时间复杂度为O(2n)．
2
16．sum = 0; i = 0;
while (i <= 100){
sum = sum + i;
i++;
}
分析：语句“sum = sum + i;”和“i++;”各执行100次，故该程序段的时间复杂度为O(1)．
17．x = 1;
s = 0;
for (i = 1; i <= n; i++){
++x;
s += x;
}
for (j = 1; j <= n; j++)
for (k = 1; k <= n; k++){
x++;
s = s + x;
}
分析：语句“++x;”执行n次，语句“x++;”和“s = s + x;”各执行2n次，故该程序段的时间复杂度为O(2n)．
第2章线性表
练习题
一、单项选择题
1．在长度为n的顺序表的第i(11)
≤≤+个位置上插入一个元素，元素的移动次数为（A）
i n
A．1
i-
n i-+B．n i-C．i D．1 2．若一个顺序表中第一个元素的存储地址为1000，每个元素占4个地址单元，那么，第6个元素的存储地址应是（A）A．1020 B．1010 C．1016 D．1024 3．带头结点的单链表（以head为头指针）为空的判断条件是（C）A．head != NULL B．head -> next == head
C．head -> next == NULL D．head == NULL
4．在单循环链表中，p指向表任一结点，判断表不是访问结束的条件是（B）A．p != NULL B．p != head C．p -> next != head D．p -> next != NULL 5．在一个单链表中，已知q指向p所指向结点的前趋结点，若在p、q所指结点之间插入一个s所指向的新结点，则执行的操作是（A）A．q -> next = s; s -> next = p B．p -> next = s; s -> next = q
C．s -> next = p -> next; p -> next = s D．p -> next = s -> next; s -> next = p 6．在一个单链表中，若删除p指向结点的后继结点，则执行的操作是（A）A．q = p -> next; p -> next = p -> next -> next; free(q);
B．p = p -> next; q = p -> next; p = q -> next; free(q);
C．q = p -> next -> next; p = p -> next; free(q);
D．p = p -> next -> next; q = p -> next; free(q);
二、填空题
7．在一个长度为n的顺序表中删除第i个元素，需要向前移动n- i个元素．
8．在顺序表中插入或删除一个元素，需要平均移动表长的一半个元素，具体移动的元素个数与插入或删除的位置有关．
9．顺序表中逻辑上相邻的元素在物理存储位置上一定相邻，链表结构中逻辑上相邻的元素在物理位置上不一定相邻．
10．已知顺序表中一个元素的存储位置是x，每个元素占c个字节，求其后继元素位置计算公式为x+ c，而已知单链表中某一结点由p指向，求此后继结点存储地址的操作为p -> next．
11．在用p指针访问单链表时，判断不是访问结束的条件是p != NULL；在访问单循环链表时，判断不是访问表结束的条件是p != head．
12．已知p指向双向链表的中间某个结点，从给定的操作语句中选择合适的填空．
（1）在p结点后插入s结点的语句序列是I、G、A、D．
（2）在p结点前插入s结点的语句序列是C、N、H、B．
（3）删除p结点的直接后继结点的语句序列是J、Q、E、M．
（4）删除p结点的直接前趋结点的语句序列是K、P、F、M．
（5）删除p结点的语句序列是O、R、L．
A．p -> next = s B．p -> prior = s C．s -> next = p
D．s -> prior = p E．p -> next = p -> next -> next F．p -> prior = p -> prior -> prior
G．p -> next -> prior = s H．p -> prior -> next = s I．s -> next = p -> next
J．q = p -> next K．q = p -> prior L．free(p)
M．free(q) N．s -> prior = p -> prior O．p -> prior -> next = p -> next P．p -> prior -> prior -> next = p Q．p -> next -> next -> prior = p R．p -> next -> prior = p -> prior 13．下面是一个在带头结点的单链表head中删除所有数据域值为x的结点的算法，但不完善，请在相应的地方填上适当的语句，使之成为完整的算法．
void DeleX(LinkList head, DataType x)
{
LinkNode *p, *q, *s;
P = head;
q = p -> next;
while (q != NULL)
if (q -> data == x)
{
s = q;
q = q -> next;
free(s);
p -> next = q;
}
else
{
p = q;
q = q -> next;
}
}
三、算法设计题
14．设有两个顺序表A和B，且都递增有序。试写一算法，从A中删除与B中相同的那些元素（即计算A - B）．
SeqList Subtraction(SeqList A, SeqList B)
{
int i, j, k = 0;//令匹配位置为0
for (i = 0; i < A.Length; i++) {
for (j = k; j < B.Length; j++)//从比较匹配的位置开始查起
if (A.Data[i] == B.Data[j])
{
k = j; //记录比较到的位置
for (j = i; j < A.Length - 1; j++)
A.Data[j] = A.Data[j + 1];//删除相同的元素
A.Length--;
break;
}
}
return A;
}
15．已知head是指向一个带头结点的单链表的头指针，p指向该链表的任一结点。试写一算法，将p 所指向的结点与其后继结点交换位置．
void Exchange(LinkList head, LinkNode *p)
{
LinkNode *q, *s, *r;
q = p -> next;
if (q != NULL)//判断所指结点是否是最后一个结点
{
if (p == head)//判断所指结点是否是头结点
{
head = head -> next;//头结点指针域所指结点变成新的头结点
s = head -> next;//记录第2个结点
head -> next = p;//新的头结点指针域指向原头结点
p -> next = s;//原头结点变成第1个结点后指针域指向第2个结点
}
else {
r = head;
while (r -> next != p)
r = r-> next;//查找p指向结点直接前趋
r -> next = q;//p指向结点直接前趋指针域指向p指向结点直接后继
p -> next = q -> next;//p指向结点指针域指向p指向结点直接后继的直接后继
q -> next = p;//p指向结点直接后继指针域指向p
}
}
else printf(“p指向的结点无后继节点!”)
}
16．已知两条单链表A和B分别表示两个集合，其元素值递增有序。试写一算法，求A和B的交集C，要求C同样以元素值递增的单链表形式存储．
LinkList Intersection(LinkList A, LinkList B)
{
LinkNode *p, *q, *r, *s;
LinkList C = (LinkNode *) malloc(SizeOf(LinkNode));
r = C; p = A; s = B;
while (p != null && q != null) {
if (p -> data < q -> data) p = p -> next;
else
if (p -> data > q -> data) q = q -> next;
else {
s = (LinkNode *) malloc(SizeOf(LinkNode));
s -> data = p -> data; s -> next = NULL; r -> next = s;
r = s; p= p -> next; q = q -> next;
}
}
}
17．设有一个带头结点的双向循环链表，head为链表的头指针。试写一算法，实现在值为x的结点之前插入一个值为y的结点．
void Insert(DlinkList head, DataType x, DataType y)
{
DlistNode *p, *s;
s = (DlistNode *) malloc(SizeOf(DlistNode));
s -> data = y;
p = head -> next;
while (p != head && p -> data != x)
p = p -> next;//查找结点值为x的结点
if (p == head)
printf(“没有值为x的结点!”);
else
{
s -> next = p;
s -> prior = p -> prior;
p -> prior -> next = s;
p -> prior = s;
}
}
第3章栈和队列
练习题
一、单项选择题
1．栈的操作原则是（C）A．顺序进出B．后进后出C．后进先出D．先进先出2．进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为（B）A．4 B．5 C．6 D．7
3．按字母a，b，c，d，e顺序入栈，则出栈的输出序列不可能是（B）A．decba B．dceab C．abcde D．edcba 4．判断一个顺序栈st（最多元素为StackSize）为栈满的条件表达式是（D）A．st.top != StackSize B．st.top != 0 C．st.top !=-1 D．st.top == StackSize - 1 5．在向顺序栈中压入元素时（C）A．先存入元素，后移动栈顶指针B．谁先谁后无关紧要
C．先移动栈顶指针，后压入元素D．同时进行
6．一个队列的入队序列是1，3，5，7，9，则出队的输出序列只能是（B）A．9，7，5，3，1 B．1，3，5，7，9
C．1，5，9，3，7 D．9，5，1，7，3
7．判断一个顺序队列sq（最多元素为QueueSize）为空队列的条件表达式为（A）A．sq.rear == sq.front B．sq.rear == 0
C．sq.front == QueueSize D．sq.rear == QueueSize + 1
8．判断一个循环队列cq（最多元素为QueueSize）为满队列的条件表达式为（C）A．cq.rear == cq.front B．cq.rear == QueueSize
C．(cq.rear + 1) % QueueSize == cq.front D．cq.rear % QueueSize + 1 == cq.front
二、填空题
9．假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX 之后，得到的输出序列为b、c、e、d、a．
10．假设S.data[maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置。能做进栈操作的条件是S.top < maxsize - 1；如果要把栈顶元素弹出到x中，需执行下列语句：x = S.data[S.top--]．11．设顺序栈存放在S.data[maxsize]中，栈底位置是maxsize - 1，则栈空条件是S.top == maxsize，栈满条件是S.top == 0．
12．若循环队列用数组data[m]存储元素值，用front和rear分别作为头尾指针，则当前元素个数为(rear - front + m) % m．
13．栈和队列都是线性结构；对于栈，只能在栈顶插入和删除元素；对于队列，只能在队尾插入元素，在队头删除元素．
14．从循环队列中删除一个元素时，其操作是先取出队头元素，后移动队头指针．
三、解答题
15．如果编号为1，2，3的3辆列车进入一个栈式结构的站台，那么可能得到的3辆列车的出栈序列有哪些？不可能出现的序列是什么？
答：可能出现的出栈序列有1、2、3，1、3、2，2、1、3，2、3、1，3、2、1，不可能出现的序列是3、1、2。
16．假设输入栈的元素为a、b、c，在栈S的输出端得到一个输出序列为a、b、c，试写出在输入端所有可能的输入序列．
答：可能的输入序列有a、b、c，a、c、b，b、a、c，c、b、a，c、a、b．
17．简述下面所给算法的功能（假设栈元素为整数类型）．
（1）void ex31(SeqStack *S)
{
int A[80], i, n = 0;
while (!empty(s)) {
A[n] = pop(s);//将栈内元素依次存入数组
n++;
}
for (i = 0; i < n; i++)
push(S, A[i]);//将数组元素依次压入栈内
}
答：该算法的功能是将通过一个数组将栈内的所有元素逆序存放．
（2）void ex32(SeqStack *S, int c)
{
SeqStack T;
int d;
while (!StackEmpty(S)) {
d = pop(S);
if (d != c)
push(T, d);
}
while (!StackEmpty(T)) {
d = pop(T);
push(S, d);
}
}
答：该算法的功能是通过一个中间栈，删除栈S中所有值为c的元素．
18．写出下列程序段的输出结果（栈结点数据域为字符型char）．
SeqStack S;
char x = ‘c’, y = ‘k’;
push(S, x);//压入’c’，栈内’c’
push(S, ‘a’);//压入’a’，栈内’ca’
push(S, y);//压入’k’，栈内’cak’
x = pop(S);//弹出’k’到x，栈内’ca’
push(S, ‘t’);//压入’t’，栈内’cat’
push(S, x);//压入’k’，栈内’catk’
x = pop(S);//弹出’k’到x，栈内’cat’
push(S, ‘s’);//压入’s’，栈内’cats’
while (!StackEmpty(S)) {
y = pop(S);
putchar(y);//依次弹出并输出栈内元素
}
putchar(x);//输出/k/
…
答：程序段的输出结果是stack．
19．在循环队列的顺序存储结构下，分别写出入队（插入元素）、出队（删除元素）时修改队尾、队头指针的操作语句以及求队列长度的公式．
答：入队时修改队尾指针的语句为cq.rear = (cq.rear + 1) % QueueSize，出队时修改队头指针的操作语句为cq.front = (cq.front + 1) % QueueSize，求队列长度的公式为(cq.rear - cq.front + QueueSize) % Queue．
四、算法设计题
20．利用两个栈S1和S2模拟一个队列，如何用栈的运算来实现队列的插入和删除运算？试写出算法．设模拟的队列如下图所示．top1为队头指针，top2为队尾指针：
void Insert(DataType x, SeqStack *S1, SeqStack *S2) {
if (top2 == S2.Size) printf(“Queue Full!”);
top2++;
if (top2 > 0)
S2.data[top2] = x;
else S1.data[top2] = x;
} DataType Delete(SeqStack *S1, SeqStack *S2) {
if (top1 >= top2) printf(“Queue Empty”);
if (top1 < 1) x = S1.data[top1];
else x = S2.data[top1];
top1++;
return x;
}
top1 = front top2 = rear
S2—→
21．试设计一个算法，实现输入一字符串并检查字符串中是否含有圆括号，当圆括号匹配时输出括号内的字符串，否则给出出错信息（提示：利用栈记录左括号出现后的字符）．
string Match() { InitStack(S);
.//初始化栈 ch = getchar(); //读取第一个字符
while (ch != ‘\n ’) { //当前字符不为结束字符时，进入循环 if (ch == ‘(‘) {
//检测到左括号 push(S,ch);
//将左括号压入栈中 ch = getchar(); //读取下一个字符
while (ch != ‘\n ’ && ch != ‘)’) {
//字符不为结束字符和右括号时，进入循环 push(S,ch);
//将字符压入栈中 ch = getchar();
//读取下一个字符
}
}
else if (ch ==’)’) {
//读取到的字符为右括号时，进入循环 while ((!StackEmpty(S)) && GetTop(S) != ‘(‘)
//栈不空且栈顶元素不为左括号，进入循环 putchar(pop(S));
//退栈并输出退栈的字符
if (StackEmpty)
//如果栈为空，表示输入字符串仅包含右括
printf (“No Match ”);
//号，输出“无匹配”信息
}
else ch = getchar();
//读取到的字符不是括号，继续读取
}
if (StackEmpty(S)) printf (“No Match ”); //如果栈为空，表示输入字符串不包含括号 }
//输出“无匹配”信息
22．试利用循环队列（长度为k ）存储，编写求斐波那契序列的前n （n k >）项（0f ，1f ，…，1n f -）
的算法，其函数定义如下：00()11(2)(1)2
n f n n f n f n n =?
?
==??-+-≥?．
int Fibonacci(int i) { if (i == 0) return 0; else if (i == 1) return 1;
else
return (Fibonacci(i - 2) + Fibonacci(i - 1));
}
void FibCirQueue(CirQueue *Q, int k, int n) { Q -> rear = 0;
for (int i = 0; i < n; i++) { Q -> rear = i;
if (i >= k) Q -> rear = Q -> rear % k;
Q -> data[Q -> rear] = Fibonacci(i); }
第4章 多维数组和广义表
练习题
一、单项选择题
1．对矩阵的压缩存储是为了 （B ）
A ．方便运算
B ．节省空间
C ．方便存储
D ．提高运算速度
2．二维数组M 的元素是4个字符（字符占一个存储单元）组成的串，行下标i 的范围是0~7，列下标j 的范围是0~9，则存放M 需要存储单元数为 （D ）
A ．360
B ．480
C ．240
D ．320
3．N 是一个5×8的二维数组，当N 按行优先方式存储时，表示该数组的第10个元素的是 （C ）
A ．N [2][2]
B ．N [2][1]
C ．N [1][1]
D ．N [1][2]
4．二维数组M [i ][j ]的元素是4个字符（字符占一个存储单元）组成的串，行下标i 的范围是0~4，列下标j 的范围是0~5，M 按行存储时元素M [3][5]的起始地址与M 按列存储时起始地址相同的是 （B ）
A ．M [2][4]
B ．M [3][4]
C ．M [3][5]
D ．M [4][4] 5．稀疏矩阵一般的压缩存储方法有两种，即 （D ）
A ．二维数组和三维数组
B ．三元组和散列
C ．顺序表和十字链表
D ．三元组和十字链表 6．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分按行序存放在一位数组[(1)/2]SA n n +中，对任一下三角部分元素()ij a i j ≥，在一维数组SA 的下标位置k 的值是
（B ）
A ．*(1)/21j j i -+-
B ．*(1)/2i i j ++
C ．*(1)/21j j i ++-
D ．*(1)/2i i j -+
二、填空题
7．将三角矩阵[8][8]A 的下三角部分逐行地存储在起始地址为1000的内存单元中，已知每个元素占4个单元，则[6][4]A 的地址为1208．
8．已知数组[10][10]A 表示对称矩阵，其中每个元素占5个单元，现将其下三角部分按行优先次序存储在起始地址为1000的连续存储单元中，则[4][5]A 对应的地址为1225．
9．广义表（（a ），a ）的表头是（a ），表尾是a ． 10．广义表（（a ））的表头是（a ），表尾是（ ）． 11．广义表（（（a ）））的表头是（（a ）），表尾是（ ）． 12．取出广义表A =（（x ，y ，z ），（a ，b ，c ，d ））中原子b 的函数是head （tail （head （tail （A ））））． 13．取出广义表A =（（x ，（a ，b ，c ，d ）））中原子c 的函数是head （tail （tail （head （tail （head （A ））））））． 14．A =（x ，（（a ，b ），c ，d ）），函数（head （head （tail （A ）））的运算结果是（a ，b ）．
三、解答题
15．已知二维数组m n A ?按“行优先顺序”存储在内存中，假设每个元素占d 个存储单元，第一个元素的存储地址表示为LOC(A [0][0])，写出计算数组A 的任一个元素LOC(A [i ][j ])的存储地址公式．
LOC(A [i ][j ])的存储地址公式为LOC(A [i ][j ]) = LOC(A [0][0]) + d * (n * i + j )．
16．已知二维数组A [5][10]按“行优先顺序”存储在内存中，假设每个元素占3个存储单元，第一个元素的存储地址LOC(A [0][0]) = 1000，计算出LOC(A [3][4])的值．
LOC(A [3][4])的值为LOC(A [3][4]) = LOC(A [0][0]) + d * (n * i + j ) = 1000 + 3×(3×10 + 4) = 1102．
17．已知有一个10阶对称矩阵A ，采用压缩存储方式存储（以行序为主，每个元素占1个单元），其起始地址为1100，写出[4][5]A 的地址．
A [4][5]的地址为1100 + d * (j * (j + 1) / 2 + i ) = 1100 + 1 × (5 × (5 + 1) / 2 + 4) = 1119．
18．求下列各广义表的表头和表尾： （1）（（a ，b ），c ，d ） （2）（a ，b ，c ） （3）（（a ，b ，c ）） （4）（a ，（b ，c ），d ） （5）（（a ，b ），（c ，（d ，（ ））））
令题中广义表皆为A ，则有：
①head （A ）=（a ，b ），tail （A ）=（c ，d ）
②head （A ）= a ，tail （A ）=（b ，c ） ③head （A ）=（a ，b ，c ），tail （A ）=（ ） ④head （A ）= a ，tail （A ）=（（b ，c ），d ） ⑤head （A ）=（a ，b ），tail （A ）=（（c ，（d ，（ ））））
19．求下列广义表的长度和深度： （1）（（a ），（（b ），c ），（（（d ）））） （2）（a ，（a ，b ），d ，e ，（（i ，j ），k ）） （3）（（a ，b ），（c ，（d ，e ）））
令题中广义表皆为A ，则有：
①length （A ）= 3，depth （A ）= 4
②length （A ）= 5，depth （A ）= 3 ③length （A ）= 2，depth （A ）= 3
20．写出下列稀疏矩阵对应的三元组表：
0010050203004
2
0????-????-??
． 三元表如下：
第5章 树和二叉树
练习题
一、单项选择题
1．将一棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根节点的编号为1，则编号为49的结点的左孩子编号为 （B ）
A ．99
B ．98
C ．50
D ．48
2．设深度为k 的二叉树上只有度为0和度为2的结点，则此类二叉树所包含的结点数至少为 （C ）
A ．1k +
B ．21k +
C ．21k -
D ．2k
3．已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，则它的前序遍历序列是 （B ）
A ．acbed
B ．cedba
C ．deabc
D ．decab
4．若某二叉树的前序遍历序列是abdgcefh ，中序遍历序列是dgbaechf ，则它的后序遍历序列是 （D ）
A ．bdgcefha
B ．gdbecfha
C ．bdgaechf
D ．gdbehfca
5．如果某二叉树的前序遍历序列是stuwv ，中序遍历序列是uwtvs ，则它的后序遍历序列是 （C ）
A ．uwvts
B ．vwuts
C ．wuvts
D ．wutsv 6．按照二叉树的定义，具有3个结点的二叉树有 （A ）
A ．5种
B ．4种
C ．3种
D ．6种 7．深度为4的二叉树至多可以有的结点数为 （D ）
A ．17
B ．13
C ．18
D ．15 8．一棵二叉树如图5.31所示，其后序遍历序列为 （C ）
A ．abdgcefh
B ．bgdaechf
C ．gdbehfca
D ．abcdefgh
9．以二叉链表作为二叉树的存储结构，在具有n 个结点的二叉链表中（n > 0），空链域的个数为（B ） A ．21n - B ．1n + C ．1n - D ．21n + 10．一棵左子树为空的二叉树在前序线索化后，其空指针域数为 （C ）
A ．0
B ．1
C ．2
D ．不确定
二、填空题
11．由二叉树的前序遍历和中序遍历或中序遍历和后序遍历可以唯一确定一棵二叉树．
12．已知二叉树的前序遍历序列为ABDCEFG ，中序遍历序列为DBCAFEG ，则后序遍历序列为DCBFGEA ． 13．深度为k 的完全二叉树至多有21k -个结点，至少有12k -个结点．
14．在任意一棵二叉树中，若度数为0的结点个数为0n ，度数为2的结点个数为2n ，则0n 等于21n +． 15．一棵二叉树的第i （1i ≥）层最多有12i -个结点．
图 5.31
三、解答题
如图
b
子为
h
0.19
四、算法设计题
22．以二叉链表作为存储结构，试利用指针数组实现编写非递归的前序遍历二叉树的算法．void Preorder(BinTree bt)
{
BinNode *s[n]; top =-1;
do {
while (bt != null) {
printf(“%c”,bt -> data); //访问根结点和子树根结点
top = top + 1;
s[top] = bt; //存父结点指针
bt = bt -> lchild; //访问左子树
}
if (top !=-1) {
bt = s[top]; //取父结点指针
top = top -1;
bt = bt -> rchild; //访问右子树
}
} while (top !=-1 && bt != null);
}
23．以二叉链表作为存储结构，其根结点指针为bt，试写从根开始按层遍历二叉树的算法．typedef struct {
int hp, tp;
BinTNode *dt[maxlen];
}lqueue;
void Layar(BinTree bt)
{
lqueue lq;
if (bt != null){
lq.hp = 0; lq.rp = 0; lq.dt[1] = bt;
do {
lq.hp = (lq.hp % maxlen) + 1;
bt = lq.dt[lq.hp];
printf(“%6d”,bt -> data);
if (bt -> lchild != null) {
lq.rp = (lq.rp % maxlen) + 1; lq.dt[rp] = bt.lchild;
}
if (bt -> rchild != null) {
lq.rp = (lq.rp % maxlen) + 1; lq.dt[rp] = bt.rchild;
}
} while (lq.hp != lq.rp);
printf(“\n”);
}
}
24．以中序线索二叉链表为存储结构，试写查找某结点*p 的中序前趋结点的算法．
BinThrNode *InorderPred(BinThrNode *p) {
BinThrNode *q; if (p -> ltag == 1)
//若p 左子树为空
return p -> lchild;
//返回左线索所指的中序前趋
else {
q = p -> lchild;
//左子树非空，从p 的左子树开始查找
while (q -> ltag == 0)
q = q -> rchild;
//右子树非空，延右链查找
return p;
}
} 第6章 图
练习题
一、单项选择题
1．在一个具有n 个顶点的无向图中，要连通全部顶点至少需要多少条边
（C ） A ．n B ．1n + C ．1n - D ．/2n 2．无向图的邻接矩阵是一个
（B ） A ．对角矩阵 B ．对称矩阵 C ．上三角矩阵 D ．零矩阵 3．采用邻接表存储的图的深度优先遍历算法类似于二叉树的
（B ） A ．按层遍历 B ．前序遍历 C ．中序遍历 D ．中序遍历 4．采用邻接表存储的图的宽度优先便利算法类似于二叉树的
（A ） A ．按层遍历 B ．前序遍历 C ．中序遍历 D ．中序遍历 5．设无向连通图G 中顶点数为n ，则图G 中最少有多少条边
（B ） A ．(1)n n - B ．1n - C ．1n + D ．2n 6．若图G 为n 个顶点的有向图，则图G 中最多有多少条边
（A ） A ．(1)n n - B ．1n - C ．(1)n n + D ．(1)/2n n + 7．在一个图G 中所有顶点度数之和等于边数的
（D ）
A ．3倍
B ．
1
2
倍 C ．4倍
D ．2倍 8．在具有n 个顶点的无向完全图G 中边的总数为
（B ） A ．1n + B ．(1)/2n n - C ．(1)n n +
D ．1n -
9．在具有6个顶点的无向图G 中至少应有多少条边才能确保是一个连通图 （D ） A ．8 B ．7 C ．6 D ．5 10．一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是
（C ）
A ．1n -
B ．1n +
C ．2n
D ．2(1)n -
v 1
v 2
v 3
v 5
v 4
图6.27 一个有向图
二、填空题
11．邻接表是图的链式存储结构．
12．一个无向连通图的生成树是含有该连通图的全部顶点的极小连通子图． 13．一个带权的无相连通图的最小生成树有一棵或多棵． 14．n 个顶点的连通图最多有(1)/2n n -条边．
15．设图G 有n 个顶点和e 条边，进行深度优先搜索的时间复杂度至多为()O n e +，进行广度优先搜索的时间复杂度至多为()O n e +．
16．在无向图G 的邻接矩阵A 中，若A [i ,j ]等于1，则A [j ,i ]等于1．
17．已知图G 的邻接表如图6.25所示，其从顶点v 1出发的深度优先搜索序列为13452v v v v v 、、、、，其从顶点v 1出发的广度优先搜索序列为13245v v v v v 、、、、． 18．已知一个有向图G 的邻接矩阵表示，计算第i 个结点的入度的方法是计算第i 列非零元素的个数．
19．图的生成树不是唯一的，一个连通图的生成树是一个极小连通子图，n 个顶点的生成树有n - 1条边．
20．对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示，则表头向量的大小为n ，所有邻接表中的结点总数是2e ．
三、应用题
21．已知一个图的邻接矩阵为011001
01111
1011011010
111
0????
??????????
，假设顶点是v 0，v 1，…，画出对应的图． 对应的图如下图所示：
22．对于如图6.27所示的有向图，试给出：
（1）图的邻接矩阵； （2）邻接表和逆邻接表； （3）强联通分量．
图的邻接矩阵为0001001010000
001110000001101000
1001
0??????
?
?????????
，邻接表、逆邻接表、强联通分量如下图所示：
图6.25 一个图的邻接表
23．按顺序输入顶点对（边）：（1，4），（2，3），（3，5），（4，5），（1，3），（3，4），（1，2），采用尾插法画出邻接表；若从顶点V3出发，分别写出按深度优先搜索遍历和按广度优先搜索遍历的顶点序列．
邻接表如图所示：
按深度优先搜索遍历的顶点序列为：V3、V4、V5、V1、V2，
按广度优先搜索遍历的定点序列为V3、V4、V1、V5、V2．
24．已知一个如图6.28所示的带权网络图，使用普里姆算法构造该图的最小生成树．
构造最小生成树的过程图如下所示：
25
．已知一个如图 6.29所示的带权网络图，使用克鲁斯卡尔算法构造该图的
最小生成树．
构造最小生成树的过程图如下所示：
26．设有一个有向图G 如图6.30所示．写出图G 的两个拓扑排序序列．
排序顺序如图所示，故拓扑排序序列为：①1、2、3、6、5、4；②1、3、2、6、5、4．
5
1
2 3
4
5
6
图6.29 一个带权图 1 2
3
8 6 5
6 7
5
1
2
3
4
5 6
图6.28 一个带权图 2 2
3
4 4
5 6
7
5
图6.30 一个有向图
1
3
(a)
2
1 3
4
(b)
2
3
1
2 3 4
(c) 2 3 4 1 2 3 4
5
(d)
2 2
3
4 1
2
3
4
5
6
(e)
2
2
3
4 4
1
2
(a)
1
1
2
3 4
1
2
(b)
1 2
3
4
(c)
1
2 3
1
2
3
4 5
1
2 3
5
(d)
1
2
3
4
5
6
1
2 3
5
5
(d)
4
(e)
4
(e)
第7章 排序
练习题
一、单项选择题
1．在下列排序方法中，时间复杂度不受数据初始状态影响，恒为2()O n 的是
（C ）
A ．堆排序
B ．冒泡排序
C ．直接选择排序
D ．快速排序 2．在待排序的记录关键字序列基本有序的前提下，效率最高的排序方法是 （B ）
A ．直接选择排序
B ．直接插入排序
C ．快速排序
D ．归并排序 3．在下列排序方法中，记录关键字比较的次数与记录的初始排列次序无关的方法是 （D ）
A ．直接插入排序
B ．冒泡排序
C ．希尔排序
D ．直接选择排序
4．在下列排序方法中，从待排序序列中依次取出记录关键字与已排序序列（初始时为空）中的记录关键字进行比较，将其放入已排序序列的正确位置上的方法，称为 （C ）
A ．直接选择排序
B ．冒泡排序
C ．直接插入排序
D ．希尔排序 5．在下列排序方法中，从待排序序列中挑选记录（关键字值大的或小的），并将其一次放入已排序序列（初始时为空）的一端的方法，称为 （B ）
A ．希尔排序
B ．直接选择排序
C ．插入排序
D ．归并排序 6．在下面的几种排序方法中，需求内存空间最大的方法是 （A ）
A ．归并排序
B ．直接选择排序
C ．快速排序
D ．插入排序 7．在下列排序方法中，平均查找长度最小的排序方法是 （D ）
A ．归并排序
B ．直接插入排序
C ．直接选择排序
D ．快速排序 8．有一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一趟排序结果为 （A ）
A ．40、38、46、56、79、84
B ．40、38、46、84、56、79
C ．38、40、46、56、79、84
D ．40、38、46、79、56、84
9．有一组记录的关键字序列，经过一次归并后为[25 48][16 35][79 82][23 40][36 72]，按归并排序的方法对该序列再进行一趟归并排序后的结果为 （C ）
A ．16、25、48、35、79、82、23、36、40、72
B ．16、25、35、48、79、82、23、36、40、72
C ．16、25、35、48、23、40、79、82、36、72
D ．16、25、35、48、79、23、36、40、72、82
10．已知一组记录的关键字序列为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆（大根堆）是 （A ）
A ．84、79、56、38、40、46
B ．79、46、56、38、40、84
C ．84、79、56、46、38、40
D ．84、56、79、40、46、38 11．若一组记录的关键字序列为（46，79，56，38，40，84），则；利用箱排序排序方法，按每个关键字个位数依次装箱后得到的结果为 （C ）
A ．38、40、46、56、79、84
B ．40、38、46、79、56、84
C ．40、84、46、56、38、79
D ．40、38、46、84、56、79
12．用快速排序方法对包含n 个记录的文件进行排序，最坏情况下执行的时间复杂度为 （D ）
A ．()O n
B ．2(log )O n
C ．2(log )O n n
D ．2()O n
二、填空题
13．在选择排序、堆排序、快速排序和直接插入排序方法中，稳定的排序方法是直接插入排序．
14．分别采用堆排序、快速排序、直接插入排序和归并排序方法对初始状态为基本递增有序的序列，按递增顺序排序，最省时间的排序方法是直接插入排序，最费时间的是归并排序．
15．在直接插入排序、希尔排序、直接选择排序、快速排序、堆排序、归并排序和基数排序中，不稳定的排序有直接选择排序、希尔排序、快速排序、堆排序，平均比较次数最少的排序是快速排序，需要内存空间最多的是基数排序．
16．在对一组关键字序列为（51，38，96，23，45，15，72，62，87）的记录进行直接插入排序时，当把第5个记录（关键字值45）插入到有序表时，为寻找插入位置需要比较3次．
17．对n 个记录的排序文件进行起泡排序时，最少的比较次数是1n -次．
18． 在所有的排序算法中，若记录关键字基本正序（升序）或反序（降序），则选用堆排序；若记录按关键字无序，则最好选用快速排序．
19．在所有的排序算法中，若记录关键字基本正需（升序），则选用直接插入排序；若初始记录关键字基本反序（降序），则选用堆排序．
20．在快速排序、归并排序和堆排序等几种排序算法中，若仅从存储空间考虑，它们的优先顺序是堆排序、快速排序、归并排序．
21．对n 个记录采用直接选择排序方法所执行的记录交换次数最多为1n -次． 22．对n 个记录进行堆排序，最坏情况下的执行时间为2(log )O n n ．
三、解答题
23．对于给定的一组关键字（46，32，55，81，65，11，25，43），进行直接插入排序，写出其排序的每一趟结果．
直接插入排序的每一趟结果为：
第一趟：[32，46]，[55，81，65，11，25，43] 第二趟：[32，46，55]，[81，65，11，25，43] 第三趟：[32，46，55，81]，[65，11，25，43] 第四趟：[32，46，55，65，81]，[11，25，43] 第五趟：[11，32，46，55，65，81]，[25，43] 第六趟：[11，25，32，46，55，65，81]，[43] 第七趟：[11，25，32，43，46，55，65，81]
24．对于给定的一组关键字（26，18，60，14，7，45，13，32），进行直接选择排序，写出其排序的每一趟结果．
直接选择排序的每一趟结果为：
第一趟：7，[18，60，14，26，45，13，32] 第二趟：7，13，[60，14，26，45，18，32] 第三趟：7，13，14，[60，26，45，18，32] 第四趟：7，13，14，18，[26，45，60，32] 第五趟：7，13，14，18，26，[45，60，32] 第六趟：7，13，14，18，26，32，[60，45] 第七趟：7，13，14，18，26，32，45，[60] 最后得到排序结果：7，13，14，18，26，32，45，60．
25．对于给定的一组关键字（41，62，13，84，35，96，57，39，79，61，15，83），分别写出执行以下各排序算法的每一趟排序结果．
（1）希尔排序（5，2，1）；（2）快速排序；（3）基数排序．
①希尔排序的每一趟结果为：
d = 5：15，57，13，79，35，41，62，39，84，61，96，83 d = 2：13，39，15，41，35，57，62，61，84，79，96，83 d = 1：13，15，35，39，41，57，61，62，79，83，84，96 ②快速排序的每一趟结果为：
第一趟：[15，39，13，35]，41，[96，57，84，79，61，62，83] 第二趟：[13]，15，[39，35]，41，[83，57，84，79，61，62]，96 第三趟：[13]，15，[35]，39，41，[62，57，61，79]，83，[84]，96 第四趟：13，15，35，39，41，[61，57]，62，[79]，83，84，96 第五趟：13，15，35，39，41，[57]，61，62，79，83，84，96 第六趟：13，15，35，39，41，57，61，62，79，83，84，96 ③基数排序的每一趟排序结果为：
第一趟：41，61，62，13，83，84，35，15，96，57，39，79 第二趟：13，15，35，39，41，57，61，62，79，83，84，96
26．对于给定的一组关键字（26，18，60，14，7，45，13，32），写出执行堆排序算法的每一趟排序结果．
初始关键字：[26，18，60，14，7，45，13，32] 初始堆：[60，32，45，18，7，26，13，14] 第一趟排序：[32，45，18，7，26，13，14]，60 重建堆：[45，32，18，26，7，14，13]，60 第二趟排序：[32，18，7，26，13，14]，45，60 重建堆：[32，26，14，18，13，7]，45，60
第三趟排序：[26，14，18，13，7]，32，45，60 第四趟排序：[14，18，13，7]，26，32，45，60 重建堆：[18，14，13，7]，26，32，45，60 第五趟排序：[14，13，7]，18，26，32，45，60 第六趟排序：[13，7]，14，18，26，32，45，60 第七趟排序：[7]，13，14，18，26，32，45，60
27．对待排序记录关键字序列，在以下几种情况下，进行直接插入排序时（按升序）至多需要进行多少次关键字的比较？
（1）关键字从小到大顺序有序（正序）； （2）关键字从大到小顺序有序（反序）．
（3）前一半关键字序列从小到大顺序有序，后一般关键字序列从大到小顺序有序．
①1n -次；②1
(1)(2)2n n -+次；③1
2
12n
n
i n i =+-+∑次．
28．判断下列序列是否为堆（大根堆或小根堆），如果不是，则将其调整为堆． （1）（17，18，60，40，7，32，73，65）； （2）（96，83，72，45，28，54，60，23，38，15）； （3）（25，48，16，35，79，82，23，40，36，72）； （4）（12，24，18，65，33，56，33，92，86，70）；
①不是堆，调整为小根堆7，17，32，40，18，60，73，65． ②是大根堆．
③不是堆，调整为大根堆82，79，25，40，72，23，16，36，35，48 ④是小根堆
一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。
2016年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共7页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。毖须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题，每小题2分，共30分> 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．下列选项中，不属于线性结构特征的是 A．数据元素之间存在线性关系 B．结构中只有一个开始结点 C．结构中只有一个终端结点 D．每个结点都仅有一个直接前趋 2．设l7个元素的顺序表中，若将第个元素e移动到第个位置，
不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是 3．若用一个大小为7的数组作为循环队列的存储结构，且当前rew和盘0nt的值分别 为2和4，在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3 个操作之前rear和矗0nt的值分别是 A．0和l B．0和3 C．3和6 D．4和5 4．已知广义表LS=(((a))，((b，(c))，(d，(e，f)))，0)，LS的长度是 A．2 B．3 C．4 D. 5 5．一棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。于中包含的结点数是 A．k B. 2k-1 C．k2 D．2k-1 6．如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序 遍历序列是 A．cedba B．decba C．ecdba D．ecbad 7．一个森林有m棵树，顶点总数为n，则森林中含有的总边数是 A．m B. n-l C．n-m D．n+m 8．设图的邻接矩阵A如下所示。各顶点的度依次是
数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。
A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。
中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A
《数据结构》期末考试试题及答案 (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)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■
2007年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码2331) 本试卷共12页，满分100分；考试时间150分钟。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下面程序段的时间复杂度为 A．O(1) B．O(log n) C．O(n) D．O(n2) 2．已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在8所指结点之后插入上述链表应执行的语句为【】 3．在计算机内实现递归算法时所需的辅助数据结构是【】 A．栈B．队列 C．树D．图 4．假设以数组A[m]存放循环A[m]的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置。则队头元素所在的存储位置为【】 5．通常将链串的结点大小设置为大于l是为了【】 A．提高串匹配效率B．提高存储密度 C．便于插入操作D．便于删除操作 6．带行表的三元组表是稀疏矩阵的一种【】 A．顺序存储结构B．链式存储结构 C．索引存储结构D．散列存储结构 7．表头和表尾均为空表的广义表是【】 A．( ) B．( ( ) ) C．( ( ( ) ) ) D．( ( )，( ) ) 8．用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为【】A．n-1 B．n C．n+l D．2n 9．为便于判别有向图中是否存在回路，可借助于【】
A．广度优先搜索算法B．最小生成树算法 C．最短路径算法D．拓扑排序算法 10．连通网的最小生成树是其所有生成树中【】 A．顶点集最小的生成树B．边集最小的生成树 C．顶点权值之和最小的生成树D．边的权值之和最小的生成树 11．按排序过程中依据的原则分类，快速排序属于【】 A．插入类的排序方法B．选择类的排序方法 C．交换类的排序方法D．归并类的排序方法 12．下列关键字序列中。构成小根堆的是【】 A．{84，46，62，41，28，58，15，37} B．{84，62，58，46，4l，37，28，15} C．{15，28，46，37，84，41，58，62} D．{15，28，46，37，84，58，62，41} 13．在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为【】A．4 B．5 C．6 D．7 14．假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为【】 A．n-1 B．n C．n+l D．n+2 15．散列文件也称为【】 A．顺序文件B．索引文件 C．直接存取文件D．间接存取文件 二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16．数据的逻辑结构描述数据元素之间的________________________，与存储方式无关。17．在一个长度为100的顺序表中删除第10个元素时，需移动________________________个元素。 18．队列的队尾位置通常是随着________________________操作而变化的。 19．两个空串联接得到的串的长度为________________________。 20．设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B[0]，元素a52存储在B[11]，则矩阵元素a36存储在B[________________________]中。 21．已知一棵哈夫曼树含有60个叶子结点，则该树中共有________________________个非叶子结点。 22．如图所示的有向图中含有________________________个强连通分量。 23．已知一组关键字为{15，36，28，97，24，78，47，52，13，86}，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是
习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图
计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编6 (总分：60.00，做题时间：90分钟) 一、单项选择题(总题数：14，分数：28.00) 1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009年 全国试题1(2)分】 A.栈 B.队列√ C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素a，b，c，d,e,j,g=g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是( )。【2009年全国试题2(2)分】 A.1 B.2 C.3 √ D.4 按元素出队顺序计算栈的容量。b进栈时栈中有a，b出栈，cd进栈，栈中有acd，dc出栈，ef进栈，栈 中有aef,fea出栈，栈空，g进栈后出栈。所以栈S的容量至少是3。 3.若元素a，b，c，d,e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。【2010年全国试题1(2)分】 A.d,c，e，b，f,a B.c，b，d,a，e，f C.b，c，a，e，f，d D.a,f，e,d,c，b √ 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。【2010年全国试题2(2)分】 A.b，a，c，d, e B.d,b，a，c，e C.d，b,c，a，e √ D.e，c，b，a，d a先入队，b和c可在a的任一端入队，选项A、B、D都符合要求，只有选项C不可能出现。双端队列出队结果的分析可参见四、36。 5.元素a，b，c，d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( )。【2011年全国试题2(2)分】 A.3 B.4 √ C.5 D.6 元素d进栈时，元素a，b，c已在栈中，d出栈后，P可以在a，b，c任一元素的前面进栈并出栈，也可以在元素a后出栈，c，b，a必须依次出栈，所以元素d开头的序列个数是4。 6.已知循环队列存储在一维数组A[0．n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是( )。[2011年全国试题3(2)分】 A.0，0 B.0，n—1 √ C.n一1，0
第1章概论 练习题 一、单项选择题 1．在数据结构中，从逻辑上可以把数据结构分为（B）A．紧凑结构和非紧凑结构B．线性结构和非线性结构 C．内部结构和外部结构D．动态结构和静态结构2．若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（D）A．顺序存储结构B．链式存储结构 C．索引存储结构D．散列存储结构 3．算法分析的两个主要方面是（B）A．正确性和简明性B．时间复杂性和空间复杂性 C．可读性和可维护性D．数据复杂性和程序复杂性4．线性表采用链式存储结构时，要求内存中可用存储单元地址（A）A．不一定连续的B．部分地址必须是连续的 C．必须是连续的D．一定是不连续的 5．算法指的是（C）A．计算机程序B．解决问题的计算方法 C．解决问题的有限运算序列D．排序算法 二、填空题 6．数据结构一般包括逻辑结构、存储结构和数据运算三个方面的内容． 7．数据的逻辑结构可分为线性结构、非线性结构两大类． 8．数据的存储结构（物理结构）一般可以用顺序存储结构、链式存储结构、索引存储结构及散列存储结构等四种存储方法表示． 9．在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑执行算法所需要的时间、执行算法所需要的存储空间及算法应易于理解、易于编程、易于调试等三点。 10．设有一批数据元素，为了最快地存取某元素，宜用顺序结构存储，为了方便的插入一个元素，宜用链式结构存储． 三、应用题 设n为正整数，利用大“O”记号，写出下列各程序段的时间复杂度． 11．for (i = 1; i <= n; i++){ y = y + 1; for (j = 1; j <= 2 * n; j++) x = x + 1; } 分析：语句“y = y + 1;”执行n次，语句“x = x + 1;”各执行2 2n次，故该程序段的时间复杂度为O(2n)．12．s = 0; while (n >= (s + 1) * (s + 1)) s = s + 1; 分析：语句“s = s + 1;．
四川大学期末考试试题 （2008-2009学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师： 1．数据类型为（）。 A）数据项的集合B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合D）关键字的集合 2．链表不具有的特点是（）。 A）可随机直接访问任一元素B）插入删除不需要移动元素 C）不必事先估计元素个数D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵A nxn压缩存储在一维数组B[m]中，则m的值至少为（）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A）2k-1-1 B）2k-1C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGH IJ 中序序列：CBEDAGHFJI 注：试题字迹务必清晰，书写工整。本题2页，本页为第1页 教务处试题编号：
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 6 (总分：88.00，做题时间：90分钟) 一、单项选择题(总题数：33，分数：66.00) 1.一棵完全二叉树又是一棵( )。【华中科技大学2006一、7(2分)】 A.平衡二叉树 B.堆√ C.二叉排序树 D.哈夫曼(Huffman)树 完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。 2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学1999一、5(2分)】 A.不确定 B.0 C.1 D.2 √ 左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。 3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学2000一、5(2分)】 A.0 B.1 √ C.2 D.不确定 4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。【南京理工大学1996 一、6(2分)】 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点√ D.X的左子树中最右叶结点 5.引入二叉线索树的目的是( )。【南京理工大学1998一、5(2分)】 A.加快查找结点的前驱或后继的速度√ B.为了能在二叉树中方便地进行插入与删除 C.为了能方便地找到双亲 D.使二叉树的遍历结果唯一 6.线素二叉树是一种( )结构。【西安电子科技大学1996一、9(2分)】 A.逻辑 B.逻辑和存储 C.物理√ D.线性 7.甩个结点的线索二叉树上含有的线索数为( )。【中山大学1998二、8(2分)】
《数据结构》试题参考答案 （开卷） （电信系本科2001级 2002年12月） 一、回答下列问题 (每题4分，共36分) 1. 某完全二叉树共有15381个结点，请问其树叶有多少个？ 答：n2=?n/2?=?15381/2?=7691(个) 2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？ 答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=1318 3. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。 答：根据 0 当j ＝1时 next[ j ]＝ max { k |1 全国2012年10月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．一个算法的时间耗费的数量级称为该算法的 A．效率B．难度 C．可实现性D．时间复杂度 2．顺序表便于 A．插入结点B．删除结点 C．按值查找结点D．按序号查找结点 3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是 A．p->next->next==head B．p->next==head C．p->next->next==NULL D．p->next==NULL 4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为 A．(rear-front+m)％m B．rear-front+1 C．(front-rear+m)％m D．(rear-front)％m 5．下列关于顺序栈的叙述中，正确的是 A．入栈操作需要判断栈满，出栈操作需要判断栈空 B．入栈操作不需要判断栈满，出栈操作需要判断栈空 C．入栈操作需要判断栈满，出栈操作不需要判断栈空 第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分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] 数据结构试卷（一） 一、选择题（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 (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的容量至少应该是（）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。 (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（）的空间复杂度最大。 (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有______关系。 2018年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共7页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间，超出答题区域无效。 第一部分选择题 一、单项选择题：本大题共l5小题，每小题2分，共30分。在每小题列出的备选项中 只有一项是最符合题目要求的。请将其选出。 1．下列数据结构中，逻辑结构不同的是 A．线性表 B．栈 C．队列 D．二叉树 2．将l6个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地址是l000，第6个元素的存储地址是1040，则最后一个元素的存储地址是 A．1112 B．1120 C．1124 D．1128 3．设栈的初始状态为空，元素1，2，3，4，5依次入栈，不能得到的出栈序列是 A．1，2，3，4，5 B．4，5，3，2，1 C．1，2，5，4，3 D．1，2，5，3，4 4．设指针变量P指向非空单链表中的结点，next是结点的指针域，则判断P所指结点为尾结点前一个结点的逻辑表达式中，正确的是 A. p->next!=NULL&&p->next一>next->next == NULL B．p->next!=NULL&&p->next->next—NULL C．p->next->next==NULL D．p->next—NULL 5．已知广义表LS=(((a，b，c)，d)，(e，(fg，(h i)))，LS的深度是 A．2 B．3 C．4 D．5 6．已知一棵完全二叉树T的第5层上共有5个叶结点，则T中叶结点个数最少是 A．5 8．8 C．10 D．27 7．已知二叉树T的前序遍历序列为a，b，c，e，d，中序遍历序列为C，e，b，d，a，则T 的后序遍历序列为 A．c，e，d,b，a B．d，e，c，b，a C．e，c，d，b，a D．e，c，b，a，d 8．有向图G有玎个顶点和e条边，G保存在邻接矩阵M中，M中0与1的个数差是 A．n(n+1)／2-e B．n(n+1)／2-2e C．n×n-e D．n×n-2e 9．有向图G中所有顶点的度数之和是24，则G中弧的数量是 A．10 B．12 C．14 D．16 10．设有向图G含有n个顶点、e条边，使用邻接表存储。对G进行深度优先搜索遍历算法的时间复杂度是 A．O(n) B．O(口) C．O(n+e) D．O(n×e) 11．对数据序列(26，14，17，12，7，4，3)采用二路归并排序进行升序排序，两趟排序后，得到的排序结果为 A．14，26，17，l2，4，7，3 B．12，l4，l7，26，3，4，7 C．14，26，12，l7，3，4，7 D．14，26，l2，l7，3，7，4 数据结构模拟试题... 一、简答题（15分，每小题3分） 1.简要说明算法与程序的区别。 2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ 3.说明在图的遍历中，设置访问标志数组的作用。 4.说明以下三个概念的关系：头指针，头结点，首元素结点。 5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？ 二、判断题（10分，每小题1分） 正确在括号内打√，错误打× ( )（1）广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。 ( )（2）在哈夫曼树中，权值最小的结点离根结点最近。 ( )（3）基数排序是高位优先排序法。 ( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。 ( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next = s; s->next = p->next; ( )（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。 ( )（7）数组元素的下标值越大，存取时间越长。 ( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。 ( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。 ( )（10）长度为1的串等价于一个字符型常量。 三、单项选择题（10分, 每小题1分） 1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序 2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该： A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是： A.head->priro==NULL B. head->next==NULL C. head->next==head D. head->next-> priro==NULL 4. 在顺序表( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比 第一章概论 一、选择题 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全国2012年10月自考数据结构(02331)试题及答案
数据结构历年真题收集第1章 绪论(含答案)
数据结构试卷及答案
最新自考02331数据结构试题及答案含评分标准资料
算法与数据结构试题及答案
数据结构试题及答案
相关主题
文本预览