北京理工大学专业课程模拟试题集 数据结构与算法
5.有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以C第一个出栈、D第二个出栈的次序有____种。 （2分）
6.若无向图中有n个结点，e条边，则它的邻接表需要________个表结点。 （2分） 7.设L是带有头结点的单链表的头指针，则判断单链表为空的条件是_______________。 （2分）
8.二维数组A中，每个元素的长度为4个字节，行下标从0到4，列下标从0到5，A按行序为主序存储时元素A[3, 5]的地址与A按列序为主序存储时元素____________________________的地址相同。 （2分） 9.数组的逻辑结构是________________的推广。 （2分）
10.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，____________________________________。 （2分）
11.在队列中，可进行删除操作的一端称为________。 （2分）
12.在待排序数据已基本有序的情况下，最佳的排序方法是________________________。 （2分）
三、问答题 （共6题,共36分）
1.请用C语言给出顺序表(线性表的顺序存储结构)的类型定义。（6分）
2.哈希查找算法与其他查找方法对比有何特点？何谓冲突？请写出两种解决冲突方法的名称。 （6分）
3.对于线性表的顺序存储结构，设起始地址为66，每个元素占5个存储单元，求第12个元素的内容存储在哪几个存储单元中。（6分）
4.对于n个顶点的无向图G，采用邻接矩阵A表示，如何判断下列问题： a.图中有多少边？
b.任意两个顶点i和j是否有边相连？ c.任意一个顶点的度是多少？ （6分）
15
北京理工大学专业课程模拟试题集 数据结构与算法
5.用一维数组存放的一棵完全二叉树如下：ABCDEFGHIJK。请画出这棵完全二叉树，并写出后序遍历该二叉树的访问结点序列。 （6分）
6.用3，6，7，8，30作为叶子结点的值生成一棵赫夫曼树，并计算该树的带权路径长度。 （6分）
四、算法题 （共2题,共16分）
1.试写出下面无头结点线性表操作算法的功能。（8分）
2.下面算法的功能是：在双向循环链表p所指结点之后插入s所指结点，所插入的元素为e。（8分）
Status ListInsert_Dul(DuLinkList &L, ElemType e)
if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s->data = e;
(1)_________________________;(2)_________________________; (3)_________________________;(4)_________________________; return OK;
16
北京理工大学专业课程模拟试题集 数据结构与算法
模拟试题二
一、单选题 （共12题,共24分）
1.对顺序表上的插入、删除算法的时间复杂度分析来说，通常以( )为标准操作。 （2分） A.条件判断 B.元素移动 C.算术表达式 D.赋值语句
2.对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用( )。 （2分） A.先序遍历 B.中序遍历 C.后序遍历 D.从根结点开始的层次遍历
3.稀疏矩阵一般的压缩存储方法有两种，即( )。 （2分）
A.二维数组和三维数组 B.三元组表和散列表 C.三元组表和十字链表 D.散列表和十字链表
4.设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为( )。 （2分）
A.1 B.2 C.3 D.4
.
5.线性表中的顺序存储结构是通过何种方式表示元素之间的关系( )。 （2分）
A.后继元素地址 B.元素的存储顺序 C.左、右孩子地址 D.后继元素的数组下标
6.( )不是队列的基本运算。 （2分）
A.判断一个队列是否为空 B.从队头删除一个元素 C.在队列第i个元素之后插入一个元素 D.读取队头元素的值
7.在数据结构中，从逻辑上可以把数据结构分为( )。 （2分） A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构
8.对一个有127个元素的顺序表中删除一个元素，平均要移动( )个元素。 （2分） A.62 B.63 C.63.5 D.64
17
北京理工大学专业课程模拟试题集 数据结构与算法
9.在以下的叙述中，正确的是( )。 （2分） A.线性表的线性存储结构优于链式存储结构
B.数据元素是数据的最小单位
C.二维数组是它的每个数据元素为一个线性表的线性表 D.数据项是数据的基本单位
10.若顺序存储的循环队列的MAXQSIZE=n，则该队列最多可存储( )个元素。 （2分） A.n B.n-1 C.n +1 D.不确定
11.对于顺序表的优缺点，以下说法错误的是( )。 （2分） A.插入和删除操作较方便
B.可以方便地随机存取表中的任一结点
C.无需为表示结点间的逻辑关系而增加额外的存储空间 D.由于顺序表要求占用连续的空间，存储分配只能预先进行
12.在一个单链表中，若删除p所指结点的后继结点，则执行( )。 （2分） A.q = p->next; p->next = q->next; free(q); 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);
二、填空题 （共12题,共24分）
1.栈又称为________________的线性表。 （2分） 2.____可以作为实现递归函数的一种数据结构。 （2分）
3.在单链表中，头指针的作用是____________________________。 （2分） 4.设L是带有头结点的单链表的头指针，则判断单链表为空的条件是
____________________________________________________________。 （2分） 5.已知一个有向图的邻接矩阵表示，则计算第i个结点的入度的方法是________________________________。 （2分） 6.深度为5的满二叉树的结点数为________。 （2分） 7.线性表的顺序存储结构称为____________。 （2分） 8.折半查找的存储结构仅限于________存储结构。 （2分）
9.具有20个记录的序列，采用起泡排序最少的比较次数为________。 （2分） 10. __________________排序方法能够每次从无序表中顺序查找出一个最小值。 （2分） 11.广义表((a))的表尾是____。 （2分）
18
北京理工大学专业课程模拟试题集 数据结构与算法
12.在顺序表中插入或者删除一个元素，平均需要移动________元素。 （2分）
三、问答题 （共6题,共36分）
1.请用C语言给出单链表(线性表的链式存储结构)的类型定义。（6分）
2.设有如图所示的逻辑结构图，请给出数据结构形式。（6分）
1 2 4 3
3.何谓哈希查找中的冲突？请写出两种解决冲突方法的名称。 （6分）
4.设哈希表表长为11，哈希函数（用除留余数法）H(key) = key mod 11，解决冲突的方法为开放定址法H(key)=(H(key)+d)mod11，对下列关键字序列{19，13，33，02，16，
i
i
24，7}，给出计算过程并构造哈希表。（6分）
5.以关键字序列{12，2，16，9，10，8，20}为例，写出执行直接插入排序算法的各趟排序结束时，关键字序列的状态。（6分）
6.设一个有序表为｛1，3，9，12，32，41，62，75，77，82，100｝，当采用折半查找值为82的结点时，几次比较后查找结束？请给出具体查找过程。（6分）
四、算法题 （共2题,共16分）
1.下面算法的功能是：将一个带头结点并且头指针为A的单链表分解成两个单链表，其中分别含有原链表中序号为奇数和偶数的元素且保持原来的相对顺序。请在空缺处填入相应的语句。（8分） void Decompose(LinkList A)
19