2012数据结构补考试卷A

湖北文理学院 2011－2012 学年度下学期《数据结构与算法》试卷A专业：计算机科学与技术姓名： 学号： 班级：一、判断题（本题共10小题，每小题1分，共计10分）。

（正确的打√，错的打×）1、顺序循环队列Q 空的条件是：Q.front==Q.rear.( )2、关键路径是始点到终点最小长度的路径。

( )3、序列（5, 6, 7, 20, 15, 8, 9, 25, 22，13）是一个堆。

( )4、在插入排序和选择排序中，若原始记录已基本有序，则较适合选用选择排序。

( )5、顺序表是随机存取，存取操作的时间为O （1）。

( )6、已知一棵二叉树的先序序列和后序序列，一定能构造出该二叉树。

() 7、有向图用邻接矩阵表示后，顶点i 的出度等于邻接矩阵中第i 行的元素个数。

( ) 8、归并排序的时间性能不随记录序列中关键字的分布而改变（与初始状态无关）。

( ) 9、在数据结构中，数据的基本单位是数据项。

（）10、对任意一个图，从某顶点出发进行一次广度优先或深度优先遍历，可访问图的所有顶点。

( )二、填空题（本题共10小题，每小题 2 分，共计 20分）。

（请将正确答案填入空格内，答案是确定和唯一的）1、任意一棵具有n 个结点的二叉树，若它有m 个叶子，则该二叉树上度为1的结点数为_____个。

2、常用算法的描述方法有：自然语言 、 、 和流程图。

3、某二叉树的先根遍历序列为IJKLMNO ，中根遍历序列为JLKINMO ，则该二叉树中根结点的右孩子是 。

4、堆排序的时间复杂性为，空间复杂性为。

5、二维数组A[6，7]，按行优先存储，每个元素占2个字节,A基址为600,则元素A[4,5]的存储地址是。

6、对广义表C=（a,（b,c,d））的运算 Tail(Tail(Head((Tail(C))))的结果是。

7、设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为_________________________________________。

得 分 评分人贵州大学2011-2012学年第二学期考试试卷 A数据结构注意事项：1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。

2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。

3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。

4. 满分100分，考试时间为120分钟。

题 号一二三四总 分统分人得 分一、单项选择题（共20分,每小题2分）1．不是四类基本逻辑结构之一的是 （ ）A 、集合 B 、链表结构C 、树形结构 D 、网状结构2．关于队列的描述，错误的是 （ ）A 、队列的头指针指下一个入队的位置B 、普通队列要求满足“先进先出”C 、使用一个队列可以模拟一个银行的多个同性质服务窗口的排队状况D 、循环队列可以采用顺序表实现3．在n 个结点的顺序表中，算法的时间复杂度是O （1）的操作是（ ）A 、访问第i 个结点（1≤i≤n ）和求第i 个结点的直接前驱（2≤i≤n ）B 、在第i 个结点后插入一个新结点（1≤i≤n ）C 、删除第i 个结点（1≤i≤n ）D 、将n 个结点从小到大排序4．下列关于串的叙述中，正确的是 （ ）A 、一个串的字符个数即该串的长度B 、一个串的长度至少是1C 、空串是由一个空格字符组成的串得 分评分人D 、两个串S1和S2若长度相同，则这两个串相等5．稀疏矩阵一般的压缩存储方法有两种，即 （）A 、二维数组和三维数组B 、三元组和散列C 、三元组和十字链表D 、散列和十字链表6．按照二叉树的定义,具有3个结点的二叉树有 （）A 、3种B 、4种C 、5种 B 、6种7．不是图的存储结构的是 （ ）A 、邻接多重表B 、十字链表C 、关联矩阵D 、可利用空间表 8．在关于动态存储管理，错误的说法是 （ ）A 、未被占用的连续地址空间称为空闲块B 、可利用空间表一般采用链表C 、针对内存申请块的大小范围较广时，应该采用首次拟合法D 、针对内存申请块的大小较均匀时，应该采用最差拟合法9．理想情况下，速度最快的查找结构的是 （ ）A 、分块索引B 、二叉排序树C 、二叉平衡树D 、哈希表10. 关于各种排序方法，错误的说法是 （ ）A 、关键字大小相同的记录，排序后先后顺序不改变，则称为此排序为稳定的B 、内部排序算法的性能由关键字比较次数和记录移动次数决定C 、冒泡排序的时间复杂度为O(nlogn)D 、堆排序使用的堆对应一棵完全二叉树二、概念填空题（共20分,每空2分）1．若使用伙伴系统进行动态存储管理，若申请32个字，选中的空闲块有128个字，则这个空闲块会被分裂为__________个块（最小块大小可以为4）。

浙江大学2012–2013学年秋学期《数据结构基础》课程期末考试试卷(A) 课程号： 211C0020_，开课学院：_计算机科学与技术_考试试卷：√A卷、B卷（请在选定项上打√）考试形式：√闭、开卷（请在选定项上打√），允许带____无___入场考试日期： 2012 年 11 月 15 日,考试时间： 120 分钟诚信考试，沉着应考，杜绝违纪。

考生姓名：学号：所属院系： _Answer SheetNOTE: Please write your answers on the answer sheet.注意：请将答案填写在答题纸上。

I. Please select the answer for the following problems. (20 points)(1) Which one of the following statements is true as N grows?a. For any x , N x grows faster than !Nb. 2)(log N grows faster than Nc. 2log N grows faster than 2)(log Nd. N grows faster than 2)(log N N(2) What is the time complexity of the following function that computes X N ?long int Pow (long int X, unsigned int N) {if (N == 0) return 1;if (N == 1) return X;if (IsEven(N)) /* IsEven(N) returns 1 if N is even, or 0 otherwise */return Pow(X, N / 2) * Pow (X, N / 2);else return Pow(X * X, N / 2) * X;} a. O(N ) b. O(N log ) c. O(N N log ) d. O(N )(3) Suppose that N integers are pushed into and popped out of a stack. The input sequence is 1, 2, …, N and the output sequence is p 1, p 2, …, p N . If p 2 = 2, then p i (i>2) must be .a. ib. i+2c. N - id. cannot be determined(4) What is the major difference among lists, stacks, and queues? a. Lists use pointers, and stacks and queues use arraysb. Stacks and queues are lists with insertion/deletion constraintsc. Lists and queues can be implemented using circularly linked lists, but stacks cannotd. Stacks and queues are linear structures while lists are not(5) For an in-order threaded binary tree, if the pre-order and in-order traversal sequences are ABCDEF and CBAEDF respectively ，which pair nodes ’ right links are both threads?a. A and Bb. B and Dc. C and Dd. B and E(6) If N keys are hashed into the same slot, then to find these N keys, the minimum number of probes with linear probing is .a. N-1b. Nc. N(N+1)/2d. N+1(7) If an undirected graph with N vertices and E edges is represented by an adjacency matrix. How many zero elements are there in the matrix? a. E b. 2E c. N 2-E d. N 2-2E(8) If a directed graph is stored by an upper-triangular adjacency matrix –- that is, all the elements below the main diagonal are zero. Then its topological order .a. exists and must be uniqueb. exists but may not be uniquec. does not existd. cannot be determined(9)Sort a sequence of nine integers {4, 8, 3, 7, 9, 2, 10, 6, 5} by insertion sort. When 2 is moved to the first position, the number 8 must be at position (start from 1) .a. 4b. 5c. 6d. 7(10)Let T be a tree of N nodes created by union-by-height without path compression, then the depth of the tree isa. N/2b. O(logN)c. O(N2)d. O(1)II. Given the function descriptions of the following two (pseudo-code) programs, please fill in the blank lines. (21 points)(1)Bubble sort is a simple sorting algorithm. Suppose we have a list of integers and want to sort them in ascending order. Bubble sort repeatedly scans the list from the head to the tail, and swaps two adjacent numbers if they are in the wrong order. Please complete the following program to implement bubble sort. (12 points)struct node{int value;struct node *next;/* some other fields */}struct node BubbleSort (struct node *h){/* h is the head pointer of the list with a dummy head node */struct node *p, *q;int flag_swap;if (!h->next) return h;do{flag_swap = 0;p = h;while (p->next->next){if (① ){flag_swap++;q = p->next;② ;③ ;④ ;}else p = p->next;}} while (flag_swap > 0);return h;}(2)The function is to perform Find as a Union/Find operation with path compression. (9 points)SetType Find ( ElementType X, DisjSet S ){ElementType root, trail, lead;for ( root = X; S[ root ] > 0; ① );for ( trail = X; trail != root; ② ) {lead = S[ trail ] ;③ ;}return root ;}III. Please write or draw your answers for the following problems on the answer sheet. (44 points)(1) A sorting algorithm is stable if for any keys K i = K j for i < j,the corresponding records R i precedes R j in the sorted list.(a)Is Heap Sort stable? Please give a proof if your answer is“YES”, else please provide a counter example. (4 points)(b)Is Quick Sort stable? Please give a proof if your answer is“YES”, else please provide a counter example. (4 points)(2)Given the adjacency list representation of a directed graph.Suppose V1 is always the first vertex being visited. Please list(a)the depth-first search sequence; (5 points)(b)the breath-first search sequence; (5 points) and(c)the strongly connected components. (3 points)(3) A binary search tree is said to be of “type A”if all the keysalong the path from the root to any leaf node are in sorted order(either ascending or descending).(a)Given four keys {1, 2, 3, 4}, please draw all the possiblebinary search trees of type A. (4 points)(b)In general, given N keys {1, 2, …, N}, how many differentbinary search trees of type A can be constructed? (3 points)(4)Given a hash table of size 13 and the hash function H(key) = keymod 13. Assume that quadratic probing is used to solve collisions.Please fill in the hash table with input numbers {2, 15, 3, 16, 6,29, 24, 28}. (4 points)(5)Given eight keys {1, 2, …, 8}. Please do the following:(a)construct a complete binary tree which is also a binary searchtree; (5 points) and(b)construct a min-heap out of the array which stores thecomplete binary tree obtained from (a). Use BuildHeap with asequence of percolate-down’s. (4 points)(c)Observe the keys on each level of the min-heap obtained from(b). Is there a pattern of ordering? Is this true for moregeneral cases? (3 points)IV. Given a tree represented by left-child-right-sibling structure, please describe an algorithm that counts the number of leaf nodes on every level.(15 points)。

北京交通大学软件学院2012―2013学年第一学期期末考试试题Data Structure and Algorithm Design(A)Class: ____Student Number: _____Name: ________ Teacher________I. Single-Choice(20 points)1. The height of a binary tree that contains 1023 elements is at most ( 1 )and at least ( 2 ).A．1022 B．1023 C．1024 D．9 E．10 F．112. If the sequence of pushing elements into a stack is a,b,c, which outputsequence is impossible?（）．A．abc B．bca C．cba D．cab3.How many minimum-cost spanning trees are there for an undirected connectedgraph with n vertices and e edges? ( )A. must be only oneB. n-1C. n-eD. not sure4. When using the adjacency matrix A to represent a undirected graph with n nodesand e edges, the degree of the node v i can be computed by formula ( ).A. B. /2 C. e /2 D.5. In the worst case, time complexity of quicksort will be degraded to ( ).A．O(n) B．O(n2) C．O(n log n)6.In order to find a specific key in an ordered list with 100 keys using binary searchalgorithm, the maximum times of comparisons is ( ).A. 25B.10C. 1D.77. Consider the following pseudo-code, which indicates part of a standard binary treealgorithm.print( node ){ print data;if( there is a left child ) print( left child );if( there is a right child ) print( right child );}Which of the following is the standard name for this algorithm? ( )A. Inorder traversalB. Preorder traversalC. Postorder traversalD. Binary search8.Which is not the property of a B-tree of order m? ( )A. The root node has m subtree at mostB. All leaf nodes are at the same level.C. The keys in every node are ordered.D. All leaf nodes are connected by links.9. Suppose that we have 1000 distinct integers, which are in the range from 0 to 50. If using Radix Sort according to the Least Significant Digit first, ( ) buckets are needed to constructed.A. 10B. 50C. 51D. 1000II. Fill in the blank (2points * 5)that of___ _ traversal algorithm for a normal tree.2. Here is a hash table, whose size is 18, hashing function isH1(key)=key%17 (% here is the modulus operator), and which usesLinear Probing strategy to cope with the collisions and inserts 26, 25, 72,38, 8, 18, 59 into the hash table in turn. The address of 59 is _ _ _.3. Given a key sequence {2，5，⑤，3}, please write its ascending orderedsequence after being sorted using heap sort. (Note 5=⑤, just 5 is before⑤in original sequence) . Please distinguish 5 and ⑤.4. If a 2-dimensions matrix A[m][n] is stored in an 1-D array withrow-major mapping, then the address of element A[i][j] relative toA[0][0] is ___ ____5. If the in-order and pre-order series of the nodes in a binary tree are“1,2,3,4,5” and “1,2,3,4,5” respectively, the p ostorder sequence shouldbe __________.III. (40 points)1. (8 points) Suppose there is a string abcadececdcdeeeded that comprisesthe characters a, b, c, d and e. We may encode the symbols usingvariable-length codes in order to make the length of string the shortest.Please draw the Huffman tree used to encode the characters, calculatethe weighted path length for the Huffman tree and write the code foreach character.(1)Draw the Huffman tree (3 points)a:2, b:1, c:4, d:5 , e: 6(3 points)(2)Calculate the weighted path length for the Huffman tree (2 points)WPL(T)= 6⨯2+5⨯2+2⨯3+1⨯3+4⨯2 =39(3)write the code for each character. (3 points) 错一个扣一分，扣光为止2. (8 points) Please respectively give two unsorted lists whose length are 4to illustrate that quick sort and selection sort are unstable.(1) An example list for quick sort and the sorting procedure using quicksort. (4 points)（4, 2, ②, 3）-------------------------- (2 points)sorting procedureThe first pass: 3,2,②,4 -------------------------（1point）The second pass: ②,2,3,4 -----------------------（1point）(2) An example list for selection sort and the sorting procedure usingselection sort. (4 points)（2，②，3，1）-------------------------- (1 points)sorting procedureThe first pass: 1,②, 3 , 2------------------------（1point）The second pass: 1,②, 3 , 2----------------------（1point）The third pass: 1,②, 2, 3 ----------------------（1point）3. (8 points) Given the key sequence (331, 166, 367, 236, 268, 137, 337,138), Please give the procedure (distributing and collecting) of sortingusing radix sort method. not necessary to write queue front and rearpointer if queue is null.(1) The first pass (3 points)(2) The second pass (3 points)(3)The third pass (2 points)4.（6 points）There are n1 nodes of degree 1，n2 nodes of degree 2，…，n m nodes of degree m in a tree of degree m，how many leaf nodes there are in the tree? Please give formula and prove your conclusion.Answer：because every node except root has one branch linked, so total nodes are equal to total branches plus one, there are n branches in node of degree n （2points）formula such as （2points）（2points）5. (10 points) Show the result of inserting { 63, 37, 48, 100, 54, 64, 27, 108, 99,42 } into(a) an empty binary search tree（2 points）(b) an initially empty A VL tree（4 points）(c) an initially empty B-tree of order 3（4 points）Answer：(1)（2）A VL （4 points）(3) B-tree （4points）IV. (10 points) Please fill in the blanks in the program which reverses a singly linked list. For example, {1,2,3,4,5,6,7,8,9,10} will become {10,9,8,7,6,5,4,3,2,1} after being reversed.#define list_init_size 100#define n 10#define len sizeof(struct node)typedef struct node{ int num; struct node *next; } lnode,*link;link llist;static int a[]={1,2,3,4,5,6,7,8,9,10};void creat(link *list)//create a singly linked list for key sequence stored in array a[]{ int i=0;lnode *p,*q;q=(struct node*)malloc(len);q->num=a[i]; *list=q;while (i<n-1){ p=(struct node*)malloc(len);i=i+1; （1）;（2）; q=p;}p->next=0;}void reverseList(link *h) // reverse the singly linked list{ lnode *p,*q, *r;p=*h; r=0;while (p){q=p; (3) ;(4) ; r = q;}(5) ;}main(){lnode *l;creat(&l); reverseList(&l);}Answer:(1) __ p->num=a[i];____(2) __ q->next=p;_______(3) __ p=p->next;_________(4) __ q->next =r;________(5) _ _*h=q;_________V.（10 points）Please read the following code, write the functions of programs and write output of the program.#include<stdio.h>#include "malloc.h"#define n 6static char ch[n]={'a','b','c','d','e','f'};static int a[n][n]={0,1,1,0,0,0, 1,0,0,1,1,0, 1,0,0,1,0,1, 0,1,1,0,0,1,0,1,0,0,0,1, 0,0,1,1,1,0};typedef struct node /*邻接表中的边结点*/{ int adjvex; struct node *next; } EdgeNode;typedef struct vnode /*邻接表中的顶点结点*/{ char vertex; EdgeNode *firstedge; } VertexNode[n];typedef struct{ int front,rear; int data[n]; } CirQueue;CirQueue *Q;int path[n],sum=0; int visited[n]; VertexNode G;void createALGraph() /*根据邻接矩阵，建无向网的邻接表表示*/ {int i,j; EdgeNode *s;for(i=0; i<n; i++){ G[i].vertex=ch[i]; G[i].firstedge=0; }for(i=0; i<n; i++){ for(j=0; j<n; j++){ if (a[i][j]==1){ s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=j; s->next=G[i].firstedge;G[i].firstedge=s;}}}}void print(){ int i; EdgeNode *s;for (i=0; i<n; i++){ s=G[i].firstedge;printf(" %c : ",G[i].vertex);while(s){ printf(" %c",G[s->adjvex].vertex);s=s->next;}printf("\n");}}int ShortestPath(int u,int v)/* 求u和v之间经过的分支数最少的路径*/ { int k,pre[n],spath[n],count=0,found=0;EdgeNode * p;if(u==v) { printf("error\n"); return 0;}Q=(CirQueue*)malloc(sizeof(CirQueue));Q->front=Q->rear=0;for(k=0;k<n;k++) { visited[k]=0; pre[k]=-1;}visited[u]=1; Q->data[Q->rear++]=u;while(!found && Q->front!=Q->rear){ k=Q->data[Q->front++];p=G[k].firstedge;while(p && !found){ if(visited[p->adjvex]==0){ pre[p->adjvex]=k;if(p->adjvex==v) {found=1; break;}visited[p->adjvex]=1;Q->data[Q->rear++]=p->adjvex;}p=p->next;}}if(found){ printf("found: ");spath[count++]=v; k=pre[v];while(k!=u) {spath[count++]=k; k=pre[k];}spath[count]=u;for(k=count;k>=0;k--) printf("%d ", spath[k]);printf("\n"); return 1;}else{printf("There is no path\n"); return 0;}}main(){ int i,j;createALGraph(); print();for(i=0;i<n;i++) { visited[i]=0; path[i]=-1;} printf("\n");printf("The shotest path is "); i=ShortestPath(0,3);}Answer:（1）function of createALGraphCreate linked adjacency list based on adjacency matrix --------------------------------------- (2 points)（2）function of the whole programFind the shortest path which includes the minimum number of branches among all paths from u to v. ---------------------- (3 points)（3）output of the program. ------------------------------- (1+4=5 points)VI. (10 points) Please describe the children-sibling link of a tree in C Language. Write a function to calculate the depth of a normal tree. (10 points)Answer：Typedef struct CSNode （2分）{ char data;struct CSNode *fch, *nsib;} CSNode, *CSTree;int TreeDepth(CSTree T){ if(!T) return 0; （2分）else { h1 = TreeDepth( T->fch ); （2分）h2 = TreeDepth( T->nsib); （2分）if(h1+1> h2) return(h1+1)else return(h2); （2分）}}。

北京师范大学2011～2012学年第 1 学期期末考试试卷（A 卷）课程名称： 数据结构 任课教师姓名： 刘玉铭卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）: 数学科学学院 专 业： 年级: 2010 姓 名： 学 号：阅卷教师（签字)：一、 单项选择题(每题2分，共10题20分）1．以下那一个术语与数据的存储结构无关？ 。

A ．栈B ．哈希表C ．线索树D ．双向链表2．链表不具有的特点是 。

A ．插入、删除不需要移动元素B ．可随机访问任一元素C ．不必事先估计存储空间D ．所需空间与线性表长度成正比3．算术表达式a+b*(c+d/e ）转为后缀表达式后为 。

装订线A．ab+cde/* B．abcde/+＊+C．abcde/*++ D．abcde＊/++4．二维数组A[10][20］采用列优先的存储方法,若每个元素占2个存储单元，设A[0］[0］的地址为100，则元素A[7]［6］的存储地址为。

A．232B．234C．390D．3925．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点,则度为0 的结点个数是 .A．9B．11C．15D．不确定6．一棵二叉树中序序列为FE ABDC，后序序列为F BADC E，则层序序列为。

A。

ABCDEF B. EFCDBA C。

FECDAB D。

EFCDAB7．在有向图G 的拓扑序列中,若顶点Vi 在顶点Vj 之前,则下列情形不可能出现的是 .A．G 中有弧〈Vi,Vj>B．G 中有一条从Vi 到Vj 的路径C．G 中没有弧<Vi,Vj〉D．G 中有一条从Vj 到Vi 的路径8．对于二叉排序树，下面的说法是正确的。

A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合B．对二叉排序树进行层序遍历可得到有序序列C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/29．一组记录的关键字为{47、75、55、30、42、90}，则用快速排序方法并以第一个记录为支点得到的第一次划分结果是 .A. 30,42,47,55，75，90B. 42,30,47，75，55,90C. 42，30，47,55，75，90D. 42，30,47，90,55,7510．下述文件中适合于磁带存储的是。

…………密…………封…………线…………内…………不…………要…………答…………题………………系 级 班 考生姓名 学号 任课教师姓名 第 选课教学班宜宾学院成人教育考试试卷(2011—2012学年第三学期） 课程名称：数据结构（Ａ卷）说明：1、本试题共 ？ 页 ？ 大题，适用于2011级 班 考试时间：90分钟 一. 选择题（每题2分，共60分）1、研究数据结构就是研究（ ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作 2、具有线性结构的数据结构是（ ）。

A. 图B. 树C. 广义表D. 栈 3、下面程序段的时间复杂度是（ ）。

for(i=0;i<m;i++) for(j=0;j<n;j++) a[i][j]=i*j;A. O(m 2)B. O(n 2)C. O(m*n)D. O(m+n) 4、若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素算法的时间复杂度（ ）。

A. O(log 2n)B.O(1)C. O(n)D.O(n 2) 5、链表不具有的特点是（ ）。

A. 可随机访问任一元素B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比6、在双向循环链表中，在p 指针所指的结点后插入一个指针q 所指向的新结点，修改指针的操作是（ ）。

A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D. q->next=p->next;q->prior=p;p->next=q;p->next=q;7、在一个长度为n 的顺序表中删除第i 个元素，需要向前移动（ ）个元素。

武汉大学计算机学院2012年－2013学年第一学期“数据结构”考试试题（A ）姓名学号(序号)_ 班号要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。

每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共30分）1. 数据结构在计算机内存中的表示是指 。

A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系2. 若线性表最常用的运算是存取第i 个元素及其前趋元素的值，则采用 存储方式节省时间。

A.单链表B.双链表C.单循环链表D.顺序表3. 在一个具有n 个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为 。

A.O(log 2n)B.O(1)C.O(n 2)D.O(n) 4. 栈和队列的共同点是 。

A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有其同点5. 判定一个循环队列Q （存放元素位置为0～QueueSize-1，front 指向队中队首元素的前一个位置，rear 指向队中队尾元素的位置）队空的条件是 。

A.Q.front==Q.rearB.Q.front+1==Q.rearC.Q.front==(Q.rear+1)%QueueSizeD.Q.rear==(Q.front+1)%QueueSize 6. 串是 。

A.不少于一个字母的序列B.任意个字母的序列C.不少于一个字符的序列D.有限个字符的序列 7. 一个n×n 的对称矩阵A ，如果采用以列优先（即以列序为主序）的压缩方式存放到一个一维数组B 中，则B 的容量为 。

A. n 2B.22nC. 2)1(+n nD.2)1(2+n8. 若一棵3次树中有a 个度为1的节点，b 个度为2的节点，c 个度为3的节点，则该树中有 个叶子节点。

A.1+2b +3cB.a +2b +3cC.2b +3cD.1+b +2c 9. 一棵完全二叉树中有501个叶子节点，则至少有 个节点。