北京理工大学专业课程模拟试题集 数据结构与算法
A.二叉树 B.队列 C.赫夫曼树 D.无向图
5.在顺序栈中插入元素时，是( )。 （2分） A.先存入元素，再移动栈顶指针 B.先移动栈顶指针，再存入元素 C.不分先后，同时进行 D.谁先谁后都可以
6.若顺序存储的循环队列的MAXQSIZE=n，则该队列最多可存储( )个元素。 （2分） A.n B.n-1 C.n +1 D.不确定
7.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。 （2分） A.操作 B.存储映像 C.关系 D.数据元素
8.在哈希函数H(key) = key%m中，一般来说，m应取( )。 （2分） A.奇数 B.偶数 C.素数 D.充分大的数
9.在顺序栈中删除元素时，是( )。 （2分） A.先删除元素，再移动栈顶指针 B.先移动栈顶指针，再删除元素 C.不分先后，同时进行 D.谁先谁后都可以
10.设p指向双链表的某一结点，则双链表结构的对称性可以用( )式来刻画。 （2分） A.p->next->next= =p->prior->prior; B.p->prior->prior= =p->next->prior; C.p->prior->next= =p->next->next; D.p->prior->next= =p->next->prior;
11.对顺序表上的插入、删除算法的时间复杂度分析来说，通常以( )为标准操作。 （2分） A.条件判断 B.元素移动 C.算术表达式 D.赋值语句
12.在顺序栈S中删除元素e时，执行( )。 （2分）
A.S.top++; e = *S.top; B.S.top--; e = *S.top; C.e = *S.top; S.top++; D.e = *S.top; S.top--;
二、填空题 （共12题,共24分）
1.若有向图中有n个结点，e条边，则它的邻接表需要____个头结点。 （2分） 2.在线性表中，一个数据元素可由若干数据项组成，在这种情况下，常将数据元素称为
25
北京理工大学专业课程模拟试题集 数据结构与算法
________。 （2分）
3.具有20个记录的序列，采用起泡排序最少的比较次数为________。 （2分） 4.若由4，6，8，10，12作为叶子结点的值生成一棵赫夫曼树，则该树的带权路径长度为________。 （2分）
5.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____________________________个结点。 （2分）
6.Kruskal算法适用于边数较____________________的图。 （2分）
7.在图形结构中，每个结点的前驱结点和后继结点可以有_________________。 （2分） 8.数据的存储结构包括顺序、链式、索引和________四种基本类型。 （2分） 9.若有向图中有n个结点，e条边，则它的邻接表需要____个表结点。 （2分） 10.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____________________________________________________________________________________________________________________________。 （2分）
11.二叉树中，度数为1的结点数等于m，度数为2的结点数等于n，那么度数为0的结点数等于____________。 （2分）
12. 深度为5的满二叉树的结点数为________。 （2分）
三、问答题 （共6题,共36分）
1.请用C语言给出单链队列(队列的链式存储结构)的类型定义。 （6分）
2.画出具有3个结点的所有树。（6分）
3.设有多项式A(x) = 1 + 3x + 2x4，试用线性链表表示。 （6分）
4.列举对于n个元素可以构造出的四种逻辑结构。 （6分）
5.根据Prim算法构造下图的最小生成树。（6分）
26
北京理工大学专业课程模拟试题集 数据结构与算法
6.何谓稳定的排序？直接插入排序和快速排序哪个是稳定的排序，哪个是不稳定的排序？（6分）
四、算法题 （共2题,共16分）
1.试写出下面算法的功能。（8分） Linklist Unknown (Linklist L) { if (L && L->next){ q = L; L = L->next; p = L;
while (p->next) p = p->next; p->next = q; q->next = NULL; return L;
2.下面算法的功能是：建立一个带有头结点的单链表，链表中存储顺序表中的已有元素。（8分）
void A(LinkList &La, SqList Lb) { La=(LinkList)malloc(sizeof (LNode)); La->next=NULL; p=La;
for (i=0; i<=Lb.length-1; i++){
27
北京理工大学专业课程模拟试题集 数据结构与算法
q=(LinkList)malloc(sizeof(LNode)); (1)_________________________; (2)_________________________ ; (3)_________________________; (4)_________________________;
模拟试题五
一、单选题 （共12题,共24分）
1.在哈希函数H(key) = key%m中，一般来说，m应取( )。 （2分） A.奇数 B.偶数 C.素数 D.充分大的数
2.线性表中的顺序存储结构是通过何种方式表示元素之间的关系( )。 （2分） A.后继元素地址 B.元素的存储顺序 C.左、右孩子地址 D.后继元素的数组下标
3.( )中任何两个结点之间没有逻辑关系。 （2分）
A.树形结构 B.线性结构 C.图结构 D.集合
4.数据的存储结构包括顺序、链式、索引和( )四种基本类型。 （2分） A.向量 B.数组 C.散列 D.集合
5.在以下的叙述中，正确的是( )。 （2分） A.线性表的线性存储结构优于链式存储结构 B.数据元素是数据的最小单位
C.二维数组是它的每个数据元素为一个线性表的线性表 D.数据项是数据的基本单位
6.设一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为95的结点时，( )次比较后查找结束。 （2分）
A.2 B.3 C.4 D.5
7.在一个单链表中，若删除p所指结点的后继结点，则执行( )。 （2分） A.q = p->next; p->next = q->next; free(q);
28
北京理工大学专业课程模拟试题集 数据结构与算法
B.p = p->next; p->next = p->next->next; free(p); C.p->next = p->next; free(p->next); D.p = p->next->next; free(p->next);
8.下列数据结构中( )是线性数据结构。 （2分）
A.二叉树 B.队列 C.赫夫曼树 D.无向图
9.数据的( )包括集合、线性结构、树形结构和图状结构四种基本类型。 （2分）
A.逻辑结构和存储结构 B.存储结构 C.逻辑结构 D.物理结构
10.设有一个二维数组A[10][20]，采用以行序为主序的存储结构，每个元素占两个空间，第一个元素的存放位置为100(十进制)，则元素A[6][6]的存放位置为( )。 （2分） A.320(十进制) B.232(十进制) C.300(十进制) D.352(十进制)
11.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。 （2分） A.操作 B.存储映像 C.关系 D.数据元素
12.二维数组A中，每个元素的长度为4个字节，行下标从0到4，列下标从0到5，A按行序为主序存储时元素A[3, 5]的地址与A按列序为主序存储时元素( )的地址相同。 （2分）
A.A[2, 4] B.A[3, 4] C.A[3, 5] D.A[4, 4]
二、填空题 （共12题,共24分）
1.在直接选择排序、起泡排序、直接插入排序方法中，不稳定的是_________________。 （2分）
2.Prim算法适用于边数较____________________的图。 （2分） 3.已知一个有向图的邻接矩阵表示，则计算第i个结点的出度的方法是________________________________。 （2分）
4.在图形结构中，每个结点的前驱结点和后继结点可以有_________________。 （2分） 5.在单链表中，头指针的作用是____________________________。 （2分）
6.二叉树中，度数为1的结点数等于m，度数为2的结点数等于n，那么度数为0的结点数等于____________。 （2分）
7.具有20个记录的序列，采用起泡排序最少的比较次数为________。 （2分） 8.按二叉树的定义，具有4个结点的二叉树有________种。 （2分）
9.二维数组A中，每个元素的长度为4个字节，行下标从0到4，列下标从0到5，A按
29