北京理工大学专业课程模拟试题集 数据结构与算法
p = A->next;
B =（LinkList）malloc(sizeof (LNode)); r = B;
while(p!=NULL && p->next!= NULL) q = p->next;
(1)_________________________; (2)_________________________; (3)_________________________; (4)_________________________; r->next=NULL;
2.阅读如下算法，给出该算法的功能。void Unknown(LinkList &L, int n) L=（LinkList）malloc(sizeof (LNode)); L->next=NULL; s=L;
for (i = n; i>0;--i){
p = (LinkList)malloc(sizeof(LNode)); p->data=i; s->next = p; s = p;
s->next = NULL;
6分） 20
（北京理工大学专业课程模拟试题集 数据结构与算法
模拟试题三
一、单选题 （共12题,共24分）
1.在顺序栈中删除元素时，是( )。 （2分） A.先删除元素，再移动栈顶指针 B.先移动栈顶指针，再删除元素 C.不分先后，同时进行 D.谁先谁后都可以
2.在哈希函数H(key) = key%m中，一般来说，m应取( )。 （2分） A.奇数 B.偶数 C.素数 D.充分大的数
3.广义表((a))的表尾是( )。 （2分）
A.a B.(a) C.( ) D.((a))
4.线性表若采用链式存储结构，要求内存中可用存储单元的地址( )。 （2分） A.必须是连续的 B.部分必须是连续的 C.一定是不连续的 D.连续不连续都可以
5.在算法的分析中，我们主要考虑算法的( )。 （2分）
A.空间复杂性 B.易读性 C.时间复杂性 D.可行性
6.( )中任何两个结点之间没有逻辑关系。 （2分）
A.树形结构 B.线性结构 C.图结构 D.集合
7.对一个有127个元素的顺序表中删除一个元素，平均要移动( )个元素。 （2分）A.62 B.63 C.63.5 D.64
8.对于稀疏矩阵的压缩存储只需存储( )。 （2分）
A.零元素 B.非零元素 C.对角线上的元素 D.所有元素
9.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 （2分）A.5 B.6 C.7 D.8
21
北京理工大学专业课程模拟试题集 数据结构与算法
10.设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为( )。 （2分）
A.1 B.2 C.3 D.4
11.连通图的生成树是( )。 （2分）
A.连通子图 B.顶点间可以无路径 C.边数为顶点数 D.极小连通子图
12.线性表中的链式存储结构是通过( )来表示元素之间的关系。 （2分） A.后继元素地址 B.元素的存储顺序 C.左、右孩子地址 D.后继元素的数组下标
二、填空题 （共12题,共24分）
1.已知一个有向图的邻接矩阵表示，则计算第i个结点的入度的方法是_______________。 （2分）
2.广义表((a))的表尾是____。 （2分）
3.在单链表中，头结点的作用是________________________。 （2分）
4.在图形结构中，每个结点的前驱结点和后继结点可以有_________________。 （2分） 5.在队列中，可进行插入操作的一端称为________。 （2分）
6.若由4，6，8，10，12作为叶子结点的值生成一棵赫夫曼树，则该树的带权路径长度为________。 （2分）
7.设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为____。 （2分）
8.在待排序数据已基本有序的情况下，最佳的排序方法是________________________。 （2分）
9.设无向图G的顶点数为n，则G最少有____条边。 （2分）
10.如一个结构中的数据中的数据元素之间存在一个对多个的关系，则称此结构为________________。 （2分）
11.实现递归调用属于____的应用。 （2分）
12.数据的存储结构包括顺序、链式、索引和________四种基本类型。 （2分）
三、问答题 （共6题,共36分）
1.请用C语言给出顺序栈(栈的顺序存储结构)的类型定义。 （6分）
22
北京理工大学专业课程模拟试题集 数据结构与算法
2.用4，6，7，8，9作为叶子结点的值生成一棵赫夫曼树。 （6分）
3.在栈的输入端有5个元素，顺序为a,b,c,d,e。能否在栈的输出端得到序列cbdae和dcabe？若能，请给出栈操作的过程，若不能，简述其理由。（6分）
4.按中序序列遍历二叉树的结果为123，请画出满足此条件的所有不同形态的二叉树。（6分）
5.以关键字序列{12，2，16，9，10，8，20}为例，写出执行起泡排序算法的各趟排序结束时，关键字序列的状态。（6分）
6.将如下树转换成二叉树。（6分）
四、算法题 （共2题,共16分）
1.阅读如下算法，给出该算法的功能。（8分） void Unknown(Queue &Q) { InitStack(S);
while(!QueueEmpty(Q)){ i=Dequeue(Q); Push(S,i);
while(!StackEmpty(S)){ i=Pop(S); Enqueue(Q,i);
23
北京理工大学专业课程模拟试题集 数据结构与算法
2.下面算法的功能是：在带头结点并且设立尾指针L的单向循环链表中第i个位置之前插入新的数据元素e。请在空缺处填入相应的语句。（8分） Status ListInsert(LinkList &L, int i, ElemType e){ LinkList p=L->next,s; int j=0;
if(i<=0||i>ListLength(L)+1) return ERROR; while (j (1)_________________; j++; } s=(LinkList)malloc(sizeof(LNode)); s->data=e; (2)_________________; (3)_________________; if( (4)_____________) L=s; return OK; 模拟试题四 一、单选题 （共12题,共24分） 1.计算机算法必须具有输入、输出和( )这五个特征。A.可行性 可移植性和可扩充性 B.可行性 确定性和有穷性 C.确定性 有穷性和稳定性 D.易读性 稳定性和安全性 2.广义表((a), (b))的表尾是( )。 （2分） A.( ) B.b C.(b) D.((b)) 3.广义表((a))的表尾是( )。 （2分） A.a B.(a) C.( ) D.((a)) 4.下列数据结构中( )是线性数据结构。 （2分） （2分） 24