模拟题一、一 单选题 1. 数据结构在计算机内存中的表示是指( )。 A. 数据的逻辑结构 B. 数据结构C. 数据的存储结构 D.数据元素2. 数据的( )包括集合、线性结构、树形结构和图状结构四种基本类型。A.逻辑结构和存储结构 B.存储结构 C.逻辑结构 D.物理结构3. 通常所说的时间复杂度是指( )。A. 语句的频度和 B. 算法的时间消耗 C. 最坏时间复杂度 D. 渐近时间复杂度4. 线性表的顺序存储结构是通过( )的方式表示元素之间的关系。 A. 后继元素地址 B. 元素的存储顺序 C. 左、右孩子地址 D. 后继元素的数组下标5. 在顺序栈 S 中插入元素 e 时，执行( )。A. S.top--; *S.top = e; B. *S.top = e; S.top++;C. *S.top = e; S.top--; D. S.top++; *S.top = e;6. 一个队列的入列序列是 1，2，3，4，则队列的输出序列是( )。A. 4，3，2，1 B. 1，4，3，2C. 1，2，3，4 D. 3，2，4，17. 对于稀疏矩阵的压缩存储只需存储( )。A. 所有元素 B. 对角线上的元素 C. 零元素 D. 非零元素8. 对二叉树从 1 开始编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用( )。A. 从根结点开始的层次遍历 B. 先序遍历 C. 中序遍历 D. 后序遍历9. 按二叉树的定义，具有 3 个结点的二叉树一共有( )种。A. 2 B. 3 C. 4 D. 510. 对于具有 n 个顶点和 e 条边的有向图，采用邻接表表示，则表头向量的大小为( )。A. n B. n+1 C. n-1 D. n+e11. 连通图的生成树是( )。A. 极小连通子图 B. 顶点间可以无路径C. 连通子图 D. 边数为顶点数 1 / 6 12. 快速排序方法在( )情况下最不利于发挥其长处。A. 被排序数据已基本有序 B. 被排序的数据量太大C. 被排序数据数目为奇数 D. 被排序数据中含有多个相同值二 填空题 1. ________中任何两个结点之间没有逻辑关系。2. 在线性表中，一个数据元素可由若干数据项组成，常将此种数据元素称为_______。3. 在一个单链表中，若删除 p 所指结点的后继结点，则执行____________________________________________________________。4. 栈的表尾称为________。5. 入队操作要修改________。6. 广义表是数据元素的有限序列，其元素可以是单个元素，也可以是________。7. 深度为 5 的满二叉树的结点数为________。8. 具有 3 个结点的树有________种。9. Prim 算法适用于边数较________的图。10. 遍历是指按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问______。11. 对二叉排序树进行________遍历，可以得到该二叉树所有结点构成的有序序列。12. 具有 20 个记录的序列，采用起泡排序最多的比较次数为________。三 问答题 1. 请用 C 语言给出顺序表的类型定义。2. 数据结构形式定义为(D, S)，其中 D = { a，b，c，d，e }，S = { R }，R = {(a, b), (b, c), (c, d), (c, e), (d, e) }，画出其逻辑结构图。 2 / 6 ABEFCGD3. 举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其效率不同。4. 将如下树转换成二叉树。5. 若某非空二叉树的先序序列和后序序列正好相同，试说明二叉树的形态及原因。6. 以关键字序列{12，2，16，9，10，8，20}为例，写出执行快速排序算法的各趟排序结束时，关键字序列的状态。四 算法题 1. 下面算法的功能是：在无头结点的线性单链表中插入元素结点，即在第 i 个位置之前插入新的数据元素 e 。请在空缺处填入相应的语句。Status ListInsert_L(LinkList &L, int i, ElemType e){//L 是该链表的头指针if(i==1) 3 / 6 { s=(LinkList)malloc(sizeof(LNode)); s->data=e; (1)_________________________; (2)_________________________; }else{ p=L;j=1; while (p&&j<i-1){p=p->next; ++j;} if(!p||j>i-1)return ERROR; s=(LinkList)malloc(sizeof(LNode)) s->data=e;(3)_______________________;(4)_________________________; } return OK;} 2. 试写出下面操作算法的功能。 void A(LinkList &La, SqList Lb) { La=(LinkList)malloc(sizeof (LNode)); La->next=NULL;p=La;for (i=0; i<=Lb.length-1; i++){ q=(LinkList)malloc(sizeof(LNode)); q->data=Lb.elem[i]; p->next=q; p=q;}q->next=NULL；}模拟题 1 答案一 单选题 1. C 2. C 3. C 4. B 5. B 6. C7. D 8. D 9. D 10. A 11. A 12. A二 填空题 1. 集合2.记录3. p->next=p->next->next;4. 栈顶5. 队尾指针 4 / 6 ABECF G D6. 广义表7. 318. 29. 多 或者 稠密10. 一次11. 中序12. 190三 问答题 1. typedef struct{ ElemType *elem; int length; int listsize; }SqList;2. 3. 如插入和删除操作，用顺序存储的方式实现效率低，而用链式存储的方式实现效率高4. 5. 先序序列是 NLR,后序序列是 LRN。要使得 NLR=LRN 成立，则 L 和 R 均为空，所以满足条件的二叉树只有一个根结点。6. [8，2，10，9] 12 [16，20][2] 8 [10，9] 12，16，202，8，9，10，12，16，20 5 / 6edcba 四 算法题 1. (1) s->next=L;(2) L=s;(3) s->next=p->next;(4) p->next=s;2. 算法的功能是：建立一个带有头结点的单链表，链表中存储顺序表中的已有元素 6 / 6