《数据结构与算法》模拟题 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/4 二、填空题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，试用线性链表表示。2/4 ABEFCGD3. 设有一个二维数组 A[10][20]，采用以行序为主序的存储结构，每个元素占两个空间，第一个元素的存放位置为 100(十进制)，求元素 A[6][8]的存放位置。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;3/4 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;}模拟题 2 参考答案一、单选题 1. C 4. C 5. C 7. C 9. D 12. A二、填空题 1. 记录2. 多个4. 后进先出5. 27. 非零元素8. 链式4/4 ABECF G D11. 中序;12. 快速排序三、解答题 1. typedef struct LNode{ElemType data;struct LNode *next;}LNode, *LinkList;3.LOC(i,j)=LOC(0,0)+(b2*i+j)L100+(20*6+8)*2=3564.5. 哈希查找算法不经过任何比较。冲突:对不同的关键字得到相同的哈希地址，这种现象称为冲突。开放定址法和链地址法6. 0 1 2 3 4 5 6 7 8 9 1033 13 02 24 16 7 19四、算法题 1. (1) p->next != NULL(2) pre = p;(3) q = p->next;(4) p = p->next;2. 算法的功能是：正位序（即从表头到表尾）建立一个带头结点的线性单链表。5/4