数据结构考试题目.doc.doc

得分 一、单项选择题（本大题共15小题，每小题1分，共15分） 说明：的答案必须写在以下答题卡上，写在别处不得分。 题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 x=2; while (xn/2) x=2*x; A. O(log2n) B. O(n) C. O(nlog2n) D. O(1) 2.在数据结构中，从逻辑上可以将之分为( D ) A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.内部结构和外部结构 D.线性结构和非线性结构 3.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式( D ) A.单链表 B.双向链表 C.单循环链表 D.顺序表 4.对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（ ） A． p-right=s; s-left=p; p-right-left=s; s-right=p-right; B． s-left=p; s-right=p-right; p-right-left=s; p-right=s; C． s-left=p; s-right=p-right; p-right=s; p-right-left=s ; D． p-right=s; p-right-left=s; s-left=p; s-right=p-right; 5.若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是 ( B ) A. d,c,e,b,f,a B. a,f,e,d,c,b C. b,c,a,e,f,d D. c,b,d,a,e,f 6.循环队列存放在一维数组A[0..M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素，初始时为空。下列判断队空和队满的条件中，正确的是（ A ） A. 队空：end1==end2; 队满：end1==(end2+1) mod M B. 队空：end1==end2; 队满：end2==(end1+1) mod (M-1) C. 队空：end2==(end1+1) mod M; 队满：end1==(end2+1) mod M D. 队空：end1==(end2+1) mod M; 队满：end2==(end1+1) mod (M-1) 7.串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？( A ) A. 数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 8.已知字符串S为“abaabaabacacaabaabcc”. 模式串t为“abaabc”, 采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5，则下次开始匹配时，i和j的值分别是？ A．i=1，j=0 B．i=5，j=0 C．i=5，j=2 D．i=6，j=2 9.已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ C ） A. 39 B. 52 C. 111 D. 119 10.给定二叉树如右图所示。设N代表二叉树的根， L代表根结点的左子树，R代表根结点的右子树。 若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是（ D ） A. LRN B. NRL C. RLN D. RNL 11.为5个字符编码，有如下4种编码方案，不是前缀编码的是（ d ） 说明：前缀码指的是，任何一个字符的编码都不是另一个字符的编码的前缀 A. 01,0000,0001,001,1 B. 011,000,001,010,1 C. 000,001,010,011,100 D. 0,100,110,1110,1100 12.对下图进行拓扑排序，可以得到不同的拓扑序列的个数是( C ) A. 4 B. 3 C. 2 D. 1 13.下列关于无向连通图特性的叙述中，正确的是（ ） Ⅰ.所有顶点的度之和为偶数。 Ⅱ.边数大于顶点个数减1. Ⅲ.至少有一个顶点的度为1 A. 只有Ⅰ B. 只有Ⅱ C. Ⅰ和Ⅱ D. Ⅰ和Ⅲ 14.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度AS