试卷一
一、选择题（本题共30分,每题2分）
1. 计算机识别、存储和加工处理的对象被统称为________。
A. 数据 B. 数据元素 C. 数据结构 D. 数据类型
2. 已知一栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列________。
A．1234 B．4321 C．2143 D．4123
3. 链表不具有的特点是________。
A. 随机访问 B. 不必事先估计所需存储空间大小
C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比
4. 设InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分别表示队列初始化、入队和出队的操作。经过以下队列操作后，队头的值是________
InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); EnQueue(Q,c); DeQueue(Q,x)
A. a B. b C.NULL D.x
5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行________。
A．p=q->next; p->next=q->next;free(p);
B．p=q->next; q->next=p; free(p);
C．p=q->next; q->next=p->next; free(p);
D．q->next=q->next->next; q->next=q; free(p);
6. 一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是________。
A．110 B．108 C．100 D．120
7. 在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素
的次数是________。
A. n-i B. n-i+1 C. n-i-1 D. i
8．下面关于线性表的叙述错误的是________。
A. 线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
9. Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。下面的程序段可以将A,B的值交换的操作序列是________。
A.Push(A) Push(B) Pop(A) Pop(B)
B.Push(A) Push(B) Pop(B) Pop(A)
C.Push(A) Pop(B) Push(B) Pop(A)
D.Push(B) Pop(A) Push(A) Pop(B)
10.下列查方法中哪一种不适合元素的链式存储结构________。
A．顺序查 B．分块查 C．二分查 D．散列查
11. 下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是________。
A.快速排序 B.希尔排序 C.堆排序 D.冒泡排序
12. 设一棵二叉树的深度为k，则该二叉树中最多有________个结点。
A． 2k-1 B. 2k C. 2k-1 D. 2k-1
13.数据结构与算法题库 下列四个选项中，能构成堆的是________。
A.75,65,30,15,25,45,20,10
B.75,65,45,10,30,25,20, 15
C.75,45,65,30,15,25,20,10
D.75,45,65,10,25,30,20,15
14. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边________。
A．n(n-1)/2 B．n-1 C．n D．n+1
15.栈和队列的共同特点是________。
A. 都是操作受限的线性表 B.都是先进后出
C. 都是后进先出 D.无共同点
二、填空题（本题共 10分，每空1分）
1.若经常需要对线性表进行查操作，则最好采用________存储结构。
2.某带头结点单链表的头指针为L，判定该单链表非空的条件________________。
3.数据的逻辑结构包括集合、________、________和图状结构四种类型。
4.图的两种遍历方式为：广度优先遍历和_______________。
5.线性表的链式存储结构中的结点包含________域和________域。
6.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_______上。
7.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedef struct {int stack[100]; int top;} seqstack;
void push(seqstack *s,int x)
{
if (s->top==99) printf(“overflow”);
else {_____(1)_______________;__(2)_______________;}
}
三、应用题（本题共40分）
1． 设散列表长度为11，散列函数h(key)=key % 11。给定的关键字为1，13，12，34，38，33，2，22。试画出用线性探查法解决冲突时所构造的散列表。并计算在查成功时候的平均查长度。（6分）
2．有一组权值14、21、32、15、28，画出哈夫曼树，并计算其WPL。（6分）
3．已知图G=(V,E)，其中V={1,2,3,4,5}, E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)}。要求完成如下操作：（6分）
（1）写出图的邻接矩阵
（2）写出采用邻接矩阵存储时，从顶点1出发的广度优先搜索遍历序列。
4．已知序列{503，87，512，61，908，170，897，275，653，462}，分别写出执行下列排序算法的各趟排序结束时，关键字序列的状态：（10分）
（1）直接插入排序
（2）基数排序
5．对于下面所示的连通图，写出由Prim算法生成的最小生成树。（5分）
6. 将下面的树转化为一棵二叉树,并写出对二叉树进行层序遍历的序列。（7分）
四、算法题（本题共20 分）
1．完成中序遍历二叉树。
Typedef struct node
{
Char data;
Struct node *lchild;
Struct node *rchild;
}BTreeNode,*LinkBtree;
Void InOrder(LinkBtree Bt_pointer)
{
If(Bt_pointer!=NULL)
{ _________(1)_____________;
__________(2)_____________;
__________(3)____________;
}
}
2.完成二分查算法：
#Define n 10
typedef int KeyType;
typedef struct
{
KeyType key;
} NodeType;
Typedef NodeType SeqList[n+1];
int BinSearch (SeqList R,KeyType k)
{
int low=1,high=n,mid;
while(_____（4）_______)
{ mid=(low+high)/2;
if(R[mid].key==k) return mid;
if(R[mid].key>k) _____（5）_____;
else ________（6）_______;
}
return 0;
}
3.编写算法实现直接插入排序。（8分）
参考答案
一、选择题（本题共30分,每题2分）
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
A | D | A | B | C | B | B | D | A | C | B | D | C | B | A |
二、填空题（本题共10分，每空1分）
1） 顺序 2）L->next!=NULL
3） 线性结构 树形结构 4） 深度优先遍历
5） 数据 指针 6）左子树
7） s->top++ s->stack[s->top]=x
三、应用题（本题共40分）
1、（6分）
H(1)=1
H(13)=2
H(12)=1 冲突 ， H1=2 冲突， H2=3
H(34)=1 冲突 ， H1=2 冲突， H2=3 冲突， H3=4
H(38)=5
H(33)=0
H(2)=2 冲突 ， H1=3 冲突， H2=4 冲突， H3=5 冲突， H4=6
H(22)=0 冲突 ， H1=1 冲突， H2=2 冲突， H3=3 冲突， H4=4 冲突，H5=5 冲突，
H6=6 冲突， H7=7
ASL=(1+1+3+4+1+1+5+8)/8=24/8=3
2、（6分）
Wpl=249
3、图的邻接矩阵：（3分） 广度优先序列： 1 2 3 4 5（3分）
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
1 0 1 0 1
0 1 0 1 0
4、 1）（503）87 512 61 908 170 897 275 653 462（5分）
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论