北理工71数据结构与算法模拟题220春答案
《数据结构与算法》模拟题2一、单选题1. 数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。
A.操作 B.存储映像 C.关系 D.数据元素2. 数据的最小单位是( )。
A. 数据结构B. 数据元素C. 数据项D. 文件3. 下列数据结构中( )是线性数据结构。
A. 二叉树 B. 无向图 C. 赫夫曼树 D.队列4. 采用链式存储结构存储线性表的优点是( )。
A.便于随机存取 B. 花费的存储空间比顺序存储少
C.便于插入和删除操作D. 数据元素的物理顺序与逻辑顺序相同5. ( )不是队列的基本运算。
A. 判断一个队列是否为空 B. 从队头删除一个元素
C. 在队列第i个元素之后插入一个元素 D. 读取队头元素的值6. 一个队列的入列序列是1,2,3,4，则队列的输出序列是( )。
A.4,3,2,1 B.3,2,4,1 C.1,4,3,2 D.1,2,3,47. 广义表((a), (b))的表尾是( )。
A.( ) B.b C. ((b)) D. (b)8. 若无向图中有n个结点，e条边，则它的邻接表需要( )个表结点。
A. n B. 2n C. 2e D. e9. 在哈希函数H(key) = key%m中，一般来说，m应取( )。
A. 奇数 B. 偶数 C. 充分大的数 D. 素数
10. 赫夫曼树的带权路径长度是( )。
A.所有叶结点带权路径长度之和B.所有结点权值之和
C.带权结点的值 D.除根以外所有结点权值之和11. 设一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为95的结点时，( )次比较后查找结束。
A.3 B.4 C.5 D.6 12. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是( )。 A. 直接插入排序 B. 快速排序
C. 冒泡排序 D. 简单选择排序二、填空题1. 在线性表中，一个数据元素可由若干数据项组成，在这种情况下，常将数据元素称为____________。2. 在图形结构中，每个结点的前驱结点和后继结点可以有_______。3. 从逻辑结构来看，线性结构的特点是____________。 4. 栈又称为________________的线性表。5. 设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为____。 6. 在队列中，可进行删除操作的一端称为________。7. 对于稀疏矩阵的压缩存储只需存储_________________。8. 邻接表是图的___________存储结构。9. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点为______个。 10. 有100个结点的树有________条边。11. 对二叉排序树进行________遍历，可以得到该二叉树所有结点构成的有序序列。 12. 起泡排序、快速排序和插入排序中，不稳定的是________。三、解答题1. 请用C语言给出单链表(线性表的链式存储结构)的类型定义。
2. 设有多项式A(x) = 1 + 3x + 2x4，试用线性链表表示。
3. 设有一个二维数组A，采用以行序为主序的存储结构，每个元素占两个空间，第一个元素的存放位置为100(十进制)，求元素A的存放位置。4. 将如下树转换成二叉树。
5. 哈希查找算法与其他查找方法对比有何特点？何谓冲突？请写出两种解决冲突方法的名称。6.设哈希表表长为11，哈希函数（用除留余数法）H(key) = key mod 11，解决冲突的方法为开放定址法Hi(key)=(H(key)+di)mod11，对下列关键字序列{19，13，33，02，16，24，7}，给出计算过程并构造哈希表。
四、算法题
1.在长度大于1的带头结点的单链表中，p为指向待处理结点的指针，pre为指向最小值结点的前驱结点的指针。下面算法的功能是：删除最小值结点。请在空缺处填入相应的语句。
void Delete(LinkList &L)
{
p = L->next;
pre = L;
q=p;
while( (1)_______________)
{
if (p->next->data < q-> data)
{
(2)____________;
(3)____________;
}
(4)____________;
}
pre->next = q->next;
free(q);
}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;
}
转载注明，无忧答案网
页:
[1]