全真试题(四) 本试卷分两部分,第一部分为选择题,1页至2页,第二部分为非选择题,3页至12页,共12页;选择 题30分,非选择题70分,满分100分。考试时间150分钟。 第一部分选择题(共30分) 单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个选项中只有一个是符合 题目要求的,请将其代码填在题后的括号内。错选或未选均无分。 1.下列各式中,按增长率由小至大的顺序正确排列的是() A. n, n!, 2, n3/ B n3/2, 2, nlogn, 2100 C: 2, logn, nlogn, n/2 D2100, logn, 2n,n" 2若要在单链表中的结点*p之后插入一个结点*s,则应执行的语句是() p->next=s; B. p->next=s; S->next=p->next C. p->next=s->next; s->next=p; D S->next=p p->next=s->next; 3.若要在O(1)的时间复杂度上实现两个循环链表头尾相接,则应对两个循环链表各设置一个指针,分别 指向() A.各自的头结点 B各自的尾结点 C.各自的第一个元素结点D.一个表的头结点,另一个表的尾结点 4栈的两种常用存储结构分别为() A顺序存储结构和链式存储结构B顺序存储结构和散列存储结构 C.链式存储结构和索引存储结构D链式存储结构和散列存储结构 5已知循环队列的存储空间为数组data[21,且当前队列的头指针和尾指针的值分别为8和3,则该队的当 前长度为() C.16 D.17 6已知在如下定义的链串结点中,每个字符占1个字节,指针占4个字节,则该链串的存储密度为() typedef struct node char date[ 8] struct node next 9 Link Str Node 7应用简单的匹配算法对主串s=“ BDBABDABDAB”与子串t=“BDA”进行模式匹配,在匹配成功时 进行的字符比较总次数为() B.9 C.10 8.二维数组A[2010].用列优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200 则元素A[8]9]的存储地址为() A.574 B.576 C.578 9.对广义表L=(a.b),c,d)进行操作tail(head(L)的结果是() B (d) D.(b) 10已知一棵树的前序序列为 ABCDEF,后序序列为 CEDFBA,则对该树进行层次遍历得到的序列为() AABCDEF B.ABCEFD C. ABFCDE D.ABCDFE 11.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构,则计算该有向图中某个顶点出度的时 间复杂度为() O(n) B O(e) O(n2) 12.在关键字序列(12,23,34,45,56,67,78,89,91)中二分查找关键字为45,89和12的结点时, 所需进行的比较次数分别为() B.4,3,3 C.3,4,4 D.3,3,4全真试题（四） 本试卷分两部分，第一部分为选择题，1 页至 2 页，第二部分为非选择题，3 页至 12 页，共 12 页；选择 题 30 分，非选择题 70 分，满分 100 分。考试时间 150 分钟。 第一部分 选择题（共 30 分） 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个选项中只有一个是符合 题目要求的，请将其代码填在题后的括号内。错选或未选均无分。 1.下列各式中，按增长率由小至大的顺序正确排列的是（ ） A. n ,n!,2n ,n3/2 B.n 3/2 ,2 n ,nlogn,2100 C.2 n , logn, nlogn, n3/2 D.2 100, logn, 2n , nn 2.若要在单链表中的结点*p 之后插入一个结点*s，则应执行的语句是（ ） A.s-＞next=p-＞next; p-＞next=s; B.p-＞next=s; s-＞next=p-＞next C.p-＞next=s-＞next; s-＞next=p; D.s-＞next=p;p-＞next=s-＞next; 3.若要在 O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别 指向（ ） A.各自的头结点 B.各自的尾结点 C.各自的第一个元素结点 D.一个表的头结点，另一个表的尾结点 4.栈的两种常用存储结构分别为（ ） A.顺序存储结构和链式存储结构 B.顺序存储结构和散列存储结构 C.链式存储结构和索引存储结构 D.链式存储结构和散列存储结构 5.已知循环队列的存储空间为数组 data[21]，且当前队列的头指针和尾指针的值分别为 8 和 3，则该队的当 前长度为（ ） A.5 B.6 C.16 D.17 6.已知在如下定义的链串结点中，每个字符占 1 个字节，指针占 4 个字节，则该链串的存储密度为（ ） typedef struct node{ char date[8]; struct node * next; } LinkStrNode; A.1/4 B.1/2 C.2/3 D.3/4 7.应用简单的匹配算法对主串 s=“BDBABDABDAB”与子串 t=“BDA”进行模式匹配，在匹配成功时， 进行的字符比较总次数为（ ） A.7 B.9 C.10 D.12 8.二维数组 A[20][10]采用列优先的存储方法，若每个元素占 2 个存储单元，且第 1 个元素的首地址为 200， 则元素 A[8][9]的存储地址为（ ） A.574 B.576 C.578 D.580 9.对广义表 L=((a,b),c,d)进行操作 tail (head (L))的结果是（ ） A.(c,d ) B.(d ) C.b D.(b) 10.已知一棵树的前序序列为 ABCDEF，后序序列为 CEDFBA，则对该树进行层次遍历得到的序列为（ ） A.ABCDEF B.ABCEFD C.ABFCDE D.ABCDFE 11.一个含 n 个顶点和 e 条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时 间复杂度为（ ） A.O(n) B.O(e) C.O(n+e) D.O(n2 ) 12.在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为 45，89 和 12 的结点时， 所需进行的比较次数分别为（ ） A.4，4，3 B.4， 3， 3 C.3，4，4 D.3，3，4