模拟题一、一单选题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，1B. 1，4，3，2C. 1，2，3，4D. 3，2，4，17. 对于稀疏矩阵的压缩存储只需存储( )。

A. 所有元素B. 对角线上的元素C. 零元素D. 非零元素8. 对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用( )。

A. 从根结点开始的层次遍历B. 先序遍历C. 中序遍历D. 后序遍历9. 按二叉树的定义，具有3个结点的二叉树一共有( )种。

A. 2B. 3C. 4D. 510. 对于具有n个顶点和e条边的有向图，采用邻接表表示，则表头向量的大小为( )。

A. nB. n+1C. n-1D. n+e11. 连通图的生成树是( )。

A. 极小连通子图B. 顶点间可以无路径C. 连通子图D. 边数为顶点数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) }，画出其逻辑结构图。

3. 举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其效率不同。

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){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 4. B 6. C7. D 10. A 12. A二填空题1. 集合2.记录5. 队尾指针6. 广义表7. 318. 29. 多或者稠密12. 190三问答题1.typedef struct{ElemType *elem;int length;int listsize;}SqList;2.3. 略4.5.略6.[8，2，10，9] 12 [16，20][2] 8 [10，9] 12，16，202，8，9，10，12，16，20四算法题1.(1) s->next=L;(2) L=s;(3) s->next=p->next;(4) p->next=s;2. 算法的功能是：建立一个带有头结点的单链表，链表中存储顺序表中的已有元素《数据结构与算法》模拟题2一、单选题1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。

ABE CF G DA.操作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,1B.3,2,4,1C.1,4,3,2D.1,2,3,47. 广义表((a), (b))的表尾是( )。

A.( )B.bC. ((b))D. (b)8. 若无向图中有n个结点，e条边，则它的邻接表需要( )个表结点。

A. nB. 2nC. 2eD. 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.3B.4C.5D.612. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是( )。

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[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;pre = L;q=p;while( (1)_______________){if (p->next->data < q-> data){(2)____________;(3)____________;}(4)____________;}pre->next = q->next;free(q);}2. 阅读如下算法，给出该算法的功能。