《数据结构》(第三版)试卷 (1)[11页]
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
试卷四 一、选择题（本题共20分，每小题1分） 1．在数据结构中，从逻辑上可以把数据结构分成 （ ） 。 A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 2．线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( ) 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续不连续都可以 3．不带头结点的单链表 head 为空的判定条件是( ) 。 A. head == NULL B. head->next ==NULL C. head->next == head D. head! = NULL 4．在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入s 结点，则执行( ) 。 A. s-next=p-next; p-next=s; B. p->next=s->next; s-next=p; C. q->next=s; s->next=p; D. p-next=s; s->next=q; 5．从一个具有n个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较( )个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 6．一个栈的入栈序列是 a，b，c，d，e，则栈的不可能的输出序列是( )。 A. edcba B. decba C. dceab D. abcde 7．判定一个循环队列 QU（最多元素为 m0）为满队列的条件是( )。 A. QU->front==QU->rear B. QU->front!=QU->rear C. QU->front==(QU->rear+1) % m0 D. QU->front!=(QU->rear+1) % m0 8．栈和队列的共同点是( ) 。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 9．数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为( ) 。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 10．广义表((a，b)，c，d)的表尾是( )。 A. a B. b C. (a，b) D. (c，d) 11．设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组 B[1，n(n-1)/2]中，对下三角部分中任一元素 ai,j(i≥j)，在一维数组 B 的下标位置k的值是（ ）。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j a1,1aa2,12,2 A............aa...an,nn,1n,213. 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是（ ）。 A. acbed B. decab C. deabc D. cedba 12. 如下图所示的 4 棵二叉树中，（ ）不是完全二叉树。 14. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。 A. 3 B. 4 C. 5 D. 6 15. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（ ）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 16．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ） 倍。 A. 1/2 B. 1 C. 2 D. 4 17．在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要（ ）条边。 A. n B. n+1 C. n-1 D. n/2 18．已知一有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是 （ ）。 A. v1，v2，v3，v5，v4 B. v1，v2，v3，v4，v5 C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2 19. 采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为（ ）。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 20．快速排序方法在（ ）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 二、填空题（本题共20分，每空1分） 1．根据数据元素之间的不同特征，通常有四类基本结构：_____、______、______和______。 2．下面程序段的时间复杂度是：______。 for (i=0；i；i++) for (j=0；j；j++)
本文来源：https://www.wddqw.com/doc/0fc834cd270c844769eae009581b6bd97f19bc9d.html