选择填空判断

1、一、判断题1. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。（ ）2. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。（ ）3. 只有用面向对象的计算机语言才能描述数据结构算法。（ × ）4. 在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。（ ）5. 数据元素是数据的最小单位。（ × ）6. 算法和程序都应具有下面一些特征：输入，输出，确定性，有穷性，可行性。（ ）7. 插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。（ × ）8. 线性表若采用

2、链式存储表示, 在删除时不需要移动元素。（ ）9. 用一组地址连续的存储单元存放的元素一定构成线性表。（ × ）10. 线性表的逻辑顺序与物理顺序总是一致的。( × )11. 线性表的顺序存储表示优于链式存储表示。( × )12.链表的每个结点中都恰好包含一个指针。（×）二、填空题1. 若经常需要对线性表进行查找操作，则最好采用 (顺序)存储结构。2. (循环)链表从任何一个结点出发，都能访问到所有结点。3. 若经常需要对线性表进行插入与删除操作，该线性表最好采用(链式)存储结构。4. 通常用时间复杂度和(空间复杂度)两种方法衡量算法的效率5. 已知一顺

3、序存储的线性表，每个元素占用k个存储单元，若第一个元素的地址为Loc1，则第i个元素的地址为( Loc1+(i-1)*k )。6. 在以L为头指针的带头结点的单链表和单循环链表中，判断链表是否为空的条件分别为(L->next=NULL和_L->next=L)。7. 顺序表中逻辑上相邻的元素的物理位置(相邻)，单链表中逻辑上相邻的元素的物理位置(不一定相邻)。8. 数据的逻辑结构包括集合、(线性结构)、树形结构和图状结构四种类型。9. 已知有实现同一功能的两个算法，其时间复杂度分别为O(log2n)和O(n)，哪个算法的效率更高？( O（log2n）)10. 在一个单链表L中，若要在

4、指针q所指结点的后面插入一个由指针p所指向的结点，则应进行的操作序列为：( p->next=q->next),q一>next=p。11. 在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对(头指针)进行特殊处理。12. 在双向链表中，每个结点含有两个指针域，一个指向(直接前驱)结点，另一个指向(直接后继)结点。13. 在非空线性表中除第一个元素外，集合中每个数据元素只有一个(直接前驱)；除最后一个元素之外，集合中每个数据元素均只有一个(直接后继)。14. 一个算法一该具有有穷性，(确定性)，可行性，输入和输出这五种特性。三、选择题1. 计算机识别、存储和加工处理的对

5、象被统称为_A_。A. 数据 B. 数据元素 C. 数据结构 D. 数据类型2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_D_。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续，不连续都可以3. 线性表若采用顺序存储结构时，要求内存中可用存储单元的地址_A_。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续，不连续都可以4. 在一个长度为n的顺序存储的线性表中，向第i个元素(1in+1)位置之前插入一个新元素时，需要移动_B_个元素。A. n-i B. n-i+1 C. n-i-1 D. i5. 在长度为n的顺序存储

6、的线性表中，删除第i个元素（1in）时，需要从前向后依次前移_A_个元素。A.n-i B.n-i+1 C.n-i-1 D.i6. 链表不具有的特点是_A_。A. 随机访问B. 不必事先估计所需存储空间大小C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比7. 在一个单链表L中，若要删除由指针q所指向结点的后继结点，则执行_D_。A. q=q->next; B. q->next=p->next;C. p=q->next; D. q->next=q->next->next;8. 在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行

7、_B_。A.p = q->next ; p->next = q->next; B.p = q->next ; q->next = p->next;C.p = q->next ; q->next = p; D.q->next = q->next->next; q->next = q;9. 在一个长度为n的顺序存储线性表中，删除第i个元素(1in)时，需要移动_A_个元素。A. n-i B. n-i+1 C. n-i-1 D. i10. 下面算法的时间复杂度为_B_。 int f( unsigned int n ) if (

8、n=0 | n=1 ) return 1; else return n*f(n-1); A. O(1) B. O(n) C. O(n2) D. O(n!)11. 下面程序段的时间复杂度为_C_。 for(int i=0; i<m; i+) for(int j=0; j<n; j+) Aij=i*j;A. O(m2) B. O(n2) C. O(m*n) D. O(m+n)12. 数据结构通常是研究数据的 A 及它们之间的联系。A存储和逻辑结构 B存储和抽象 C理想和抽象 D理想与逻辑13. 算法分析的目的是_B_A、找出数据结构的合理性 B、分析算法的效率以求改进、研究算法中的C、

9、输入和输出的关系D、分析算法的易懂性和文档性14. 算法分析的两个主要方面是：AA 空间复杂性和时间复杂性 B 正确性和简明性C 可读性和文档性 D 数据复杂性和程序复杂15. 线性表在 B 情况下适用于使用链式结构实现。A 需经常修改中的结点值 B 需不断对进行删除插入 C 中含有大量的结点 D 中结点结构复杂四、程序题typedef struct LNode int data; struct LNode *next;LNode, *LinkList;1. 将下面算法填完整。void ListInsert_L(node L,int i,elementtype x) LinkList p=L,

10、s; int k=0; while (&&) ;k+; if (!p |j>i-1) return ERROR;s=(LinkList) malloc (sizeof(node); s->data=x; ; ;1Pk<i-1p=p->nexts->next=p->next;p->next=s;2. 简述下面算法的功能void AC (LinkList &L) / L为一个无头结点的单链表if (L&&L->next) q=L; L=L->next; p=L; while (p->next) p=

11、p->next; p->next=q; q->next=NULL; 将该单链表的表头元素移到表尾3. 简述下面算法的功能void AE (LNode *s, LNode *q) p=s;while (p->next!=q) p=p->next;p->next=s;void AD (LNode *pa, LNode *pb) / pa和pb分别指向单循环链表中的两个结点AE (pa, pb);AE (pb, pa);将一个单循环链表拆分成两个单循环链表(指针pa和pb分别指向这两个单循环链表中的某两个节点)4.下列算法为删除带头结点的单链表head中值为x的算

12、法，将程序填完整(每空2分)已知结构体：typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;void del(LinkList head) q=head; ;while(p && ) q=p;_;if(p= = null) printf(“error”);else_;free(p);printf(“success!”);p=q->nextp->data!=xp=p->nextq->next=p->next5.下列算法为删除单链表中值为X的算法，将程序填完整（4

13、分，每空2分）已知结构体： struct node ElemType data; struct LNode *next; void del(struct node *head)  q=head;p=q->next;while(p )&&(p->data!=x ) q=p;_ _;if(p= = null) printf(“error”);else_ _;free(p);printf(“success!”);p=q->nextq->nex=p->next6.下列算法为利用尾插法，建立一个单链表，将程序填完整程序void Creat

14、eList (LinkList &L,int n)LinkList r,p;int i;L=(LinkList)malloc(sizeof(node);L->next=NULL; ;for(i=n;i>0;-i)p=(LinkList)malloc(sizeof(node);scanf(“%c”,&p->data); ;r->next=p; ;r=L;p->next=NULL;r=p;队栈串数组广义表一、判断题：1. 递归的算法简单、易懂、容易编写，而且执行效率也高。（ f ）2. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。（

15、t ）3. 堆栈、队列和数组的逻辑结构都是线性表结构。（ t ）4. 单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点 （f ）5. 若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。（t ）6. 栈和队列都是限制取点的线性结构（ t ）7. 栈和队列都是顺序存取的线性表, 但它们对存取位置的限制不同。（ t ）8. 稀疏矩阵压缩存储后，必会失去随机存取功能。（ t ）9. 如果两个串中含有相同的字符，则这两个串相等（ f ）10. 广义表的表头和表尾既可以是单元素,也可以是广义表。（ f ）二、填空题：1. 在初始为空的队列中插入元

16、素A,B,C,D以后，紧接着做了两次删除操作，此时的队尾元素是_d_。2. 已知循环队列的存储空间为数组a21，且头指针（指向队头元素）和尾指针（队尾元素的下一位置）分别为8和3，则该队列的当前长度为_16_。3. 栈结构允许进行删除操作的一端为_栈顶_。4. 队列又称为_先进先出_的线性表5. 对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为_(r+n)-f_。6. 队列的特点是_先进先出_。7. 栈又称为先进后出的线性表，队列又称为先进先出的线性表。8. 设数组Am为循环队列Q的存储空间，font为头指针，rear为尾指针，判定Q为空队

17、列的条件_front=rear_。9. 设元素1,2,3,4,5依次进栈S，若要在输出端得到序列34251，则应进行的操作序列为：push(S,1)，push(S,2)，push(S,3)，pop(S)，push(S,4)，pop(S)，pop(S)，push(S,5)，pop(S)，pop(S)。10. 一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子序列的串称为 主串，该子序列在串中的位置用子串的第一个字符在主串中的位置来表示。11. 在串的链式存储方式中，结点越大，运算处理越不方便（方便/不方便），存储占用量越小（大/小）。12. 求串T在主串S中首次出现的位置的操作是_模式

18、匹配_。13. 广义表（A,(a,b),d,e,(i,j),k)）,则广义表的长度为5，深度为3，表头为A，表尾为(a,b),d,e,(i,j),k)。14. 已知广义表ls=(a,(b,c,d),e),运用head和tail函数取出ls中的原子b的运算是_head(head(tail(ls)_。15. 设有二维数组A56，其每个元素占两个存储单元，第一个元素的存储地址为1100，若按行优先顺序存储，则元素A23的存储地址为1130，按列优先顺序存储，元素A23的存储地址为1134。 16. 设有二维数组A919(下标从0开始)，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺

19、序存储，按列优顺序存储，元素A6,6的存储地址为_220_。17. 设二维数组Amn按列优先存储，每个元素占1个存储单元，元素A00的存储地址loc(A00)，则Aij的存储地址loc(Aij)= _ loc（a00）+(j*m+i)*1_。18.三、选择题：1. 判定一个栈ST（最多元素为m0）为空的条件是_b_2. AST->top<>0 BST->top=0 CST->top<>m0 DST->top=m03. 链式栈与顺序栈相比，一个比较明显的优点是_b_。 A. 插入操作更加方便 B. 通常不会出现栈满的情况 C. 不会出现栈空的情况

20、D. 删除操作更加方便 4. 假定一个顺序队列的队首和队尾指针分别为front和rear，则判断队空的条件是_d_。A. front+1= =rear B. rear+1= =front C. front= =0 D. front= =rea5. 队和栈的主要区别是_d_A.逻辑结构不同 B.存储结构不同C.所包含的运算个数不同 D.限定插入和删除的位置不同6. 假定利用数组aN循环顺序存储一个队列，用front(指向队首元素)和rear(指向队尾元素的下一位置)分别表示队首和队尾指针，并已知队列未空，当出队并返回队首元素时所执行的操作为_d_。A. return a+rear%N; B. r

21、eturn a-rear%N;C. return a+front%N; D. return afront+%N;7. 入栈次序是a,b,c,d,e，则出栈次序不可能是_c_。Ae,d,c,b,a Bd,e,c,b,a Cd,c,e,a,b Da,b,c,d,e8. 由两个栈共享一个向量空间的好处是_b_。 A减少存取时间,降低下溢发生的机率 B节省存储空间,降低上溢发生的机率C减少存取时间,降低上溢发生的机率 D节省存储空间,降低下溢发生的机率9. 假定利用数组aN顺序存储一个栈，用top表示栈顶指针，top = = 0表示栈空，并已知栈未满，当元素x进栈时所执行的操作为_D_。A. a-to

22、p = x; B. atop- = x; C. a+top = x; D. B. atop+ = x;10. 假定利用数组aN顺序存储一个栈，用top表示栈顶指针，top = = 0表示栈空，并已知栈未空，当出栈并返回栈顶元素时所执行的操作为_A_。A. return a-top; B. return atop-; C. return a+top; D. return atop+;11. 假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是_D_。A.f+1=r B.r+1=f C.f=0 D.f=r12. 若让元素1,2,3依次进栈，则出栈次序不可能出现_C_种情况。A. 3

23、,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,213. 当利用大小为N的一维数组存储一个循环队列时，则该队列的最大长度为_B_。A. N-2 B. N-1 C. N D. N+114. 假定利用数组aN循环顺序存储一个队列，用front和rear分别表示队首和队尾指针，并已知队列未满，当元素x入队时所执行的操作为_B_。A. a+rear%N=x; B. arear+%N=x; C. a-rear%N=x; D. arear-%N=x;15. 如下陈述中正确的是_A_。A. 串是一种特殊的线性表 B. 串的长度必须大于零C. 串中元素只能是字母 D. 两个串s1和s2若长度相同，

24、则这两个串相等16. 如下陈述中正确的是_A_。A. 串是一种特殊的线性表 B. 串的长度必须大于零C. 串中元素只能是字母 D. 空串就是空白串17. 在以下的叙述中，正确的是_A_。A. 二维数组可以看做它的每个数据元素为一个线性表的线性表 B. 栈的操作方式是先进先出C. 线性表的线性存储结构优于链表存储结构D. 队列的操作方式是先进后出。18. 一个非空广义表的表头_D_。A不可能是子表B只能是子表C只能是原子D可以是子表或原子19. 在目标串T0n-1=”xwxxyxy”中，对模式串p0m-1=”yy”进行子串定位操作的结果_A_A.0 B.2C.3 D.520. 数组A中,每个元素

25、的长度为3字节,行下标从1到8,列下标从1到10,从首地址SA开始连续存放在存储器中,按行存放时,元素a85地址为( C )A SA+141B SA+180C SA+222D SA+22521. 串是一种特殊的线性表，其特殊性体现在：BA可以顺序存储 B数据元素只能来自字符集 C可以链式存储 D数据元素可以是多个字符五、算法1. Q 是一个循环队列，请分别写出插入和删除一个元素的算法#define MAXSIZE 100/最大队列长度typedef structQElemType *base; int front,rear ; SqQueue;（以下算法3分：） int EnQueue( Sq

26、Queue &Q,QElemType x ) /Q是一个循环队列，若队列不满，则将x插入并返回1；否则返回0if (Q.rear +1)%MAXSIZE = = Q.front) return 0; / 队列满 Q.baseQ.rear=x; Q.rear= (Q.rear +1)% MAXSIZE; return 1; （以下算法3分：）int DeQueue( SqQueue& Q, QElemType &x ) /Q 是一个循环队列，若队列不空，则删除队头元素并由x带回， /且返回1；否则返回0if (Q.front = = Q.rear) return 0; e

27、lse x=Q.baseQ.front; Q.front= (Q.front + 1 ) % MAXSIZE; return 1;)1. 已知：Q 是一个循环队列， 并且已知下列定义：#define MAXSIZE 100typedef structQElemType baseMAXSIZE; int front,rear ; SqQueue;约定：顺序队中,非空队中，头指针始终指向队列头元素的前一个元素，而尾指针始终指向队列尾元素。 请写出插入一个元素的算法（6分，每空2分）int EnQueue( SqQueue &Q,QElemType x )if () return 0; Qr

28、ear=; Qbase=x; return 1; 四算法分析简述下列算法的功能（栈和队列的元素类型为int）1. Status AA (Stack S) int i, n, A255;n=0;while (!StackEmpty (S) n+; Pop (S,An);for (i=1; i<=n; i+) Push (S, Ai);栈S就地逆置。2. Status AB (Stack S, int e) Stack T; int d; InitStack (T); while (!StackEmpty (S) Pop (S, d); if (d!=e) Push (T, d); whil

29、e (!StackEmpty (T) Pop (T, d); Push (S, d); 删除栈S中值等于e的元素。3. void AC (Queue &Q) Stack S; int d; InitStack (S); while (!QueueEmpty(Q) DeQueue (Q, d); Push (S, d); while (!StackEmpty(S) Pop (S, d); EnQueue (Q, d); 队列Q就地逆置。4. 简述下面算法的功能。（2分） void conversion( ) initstack(s);/初始化栈 scanf (“%d”,n); while

30、(n) push(s,n%8); n=n/8; while(! Stackempty(s) / Stackempty(s)为栈判空 pop(s,e); printf(“%d”,e); 功能是：十进制数转化成八进制数。树一、 判断题：1.二叉树是一棵无序树。（×）2.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。（）3.度为二的有序树等价于二叉树。（）4.树的带权路径长度最小的二叉树中必定没有度为1的结点。（）5.哈夫曼树一定是满二叉树。（×）6.满二叉树也是完全二叉树。（）7.设与一棵树T所对应的二叉树为BT，则与T中

31、的叶子结点所对应的BT中的结点也一定是叶子结点。（×）8.将一棵树转换成二叉树后，根结点没有左子树(×)9.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（）10用二叉树的前序遍历和中序遍历可以导出树的后序遍历。（）11.在完全二叉树中,若某结点无左孩子,则它必是叶结点。（）。12任何一棵二叉树都有n0=n2+1的关系式。（）13已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。（ ）二、填空题19. 假定一棵二叉树的结点个数为32，则它的最小深度为_6_。20. 假定一棵树的广义表表示为A(B(C, D(E, F,G), H(I, J)，则结点H的双亲结

32、点为_B_。21. 在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有_6_个。树的双亲表示法便于实现涉及到_双亲_的操作，孩子表示法便于实现涉及到孩子的操作。ABCDEF22. 对于一颗具有n个结点的二叉树，对应二叉链表中指针域有_n-1_个用于指向子结点。23. 下图所示二叉树存储在一维数组中，则元素F的下标位置为_11_。（A为1）24. 高度为k的二叉树具有的结点数目，最少为_ K _,最多为_2K-1_。25. 对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=_ n2+1_。26. 一棵含有16个结点的完全二叉树，对他按层编号，对于编

33、号为7的结点，他的双亲结编号点为_3_左孩子编号为_14_、右孩子编号为_15_。27. 在含100个结点的完全二叉树，叶子结点的个数为_50_。28. 度数为0的结点，即没有子树的结点叫作_叶子_结点。同一个结点的儿子结点之间互称为_兄弟_结点。29. 若一棵完全二叉树含有121个结点，则该树的深度为_7_。30. 已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为_ ABCDFE _。三、选择题1. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_C_。A. n B. n-1 C. n+1 D. 2*n2. 在一棵二叉树的第5层上，最多具有

34、_B_个结点。A. 14 B. 16 C. 31 D. 323. 在一棵深度为h的完全二叉树中，所含结点个数不少于_D_。A. 2h B. 2h+1 C. 2h -1 D. 2h-14. 一棵树的广义表表示为a(b(c), d(e(g(h), f)，则该二叉树的高度为_D_。A. 2 B. 3 C. 4 D. 55. 将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为_A_。A.30 B.31 C.16 D.326. 在一棵树中，每个结点最多有_B_个直接前驱结点。A. 0 B. 1 C. 2 D. 任意多个7. 7. 树中

35、所有结点的度数之和等于结点总数加_C_。A. 0 B. 1 C. -1 D. 28. 二叉树中第5层上的结点个数最多为_C_A.8 B.15C.16 D.329. 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为_A_。A.98 B.99 C.50 D.4810. 由权值分别为3, 8, 6, 2, 5的叶子结点生成一颗赫夫曼树，它的带权路径长度为_D_。A. 24 B. 48 C. 72 D. 5311. 把一棵树转换为二叉树后，这棵二叉树的形态是 A 。A.唯一的 B.有多种C.有多种，但根结点都没有左孩子 D.有多

36、种，但根结点都没有右孩子12. 具有n(n>0)个结点的完全二叉树的深度为 C 。A élog2(n)ù B ë log2(n)û C ë log2(n) û+1 D élog2(n)+1ù算法：1. 假设二叉树采用链表存储结构，设计一个算法计算一棵给定二叉树的叶子结点数。请先写出存储结构，然后再完成算法。存储结构定义：typedef struct BiTNode / 结点结构 Selemtype data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;

37、 int leafs(BTree *b)int num1,num2;if(b= =NULL)return 0;else if(b->lchild = =NULL && b->rchild= =NULL)return 1;elsenum1=leafs(b->lchild);num2=leafs(b->rchild);return(num1+num2);或：void CountLeaf (BiTree T, int& count) if ( T ) if (!T->lchild)&& (!T->rchild) count+

38、; / 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); / if / CountLeaf图一、 判断题：1.在AOE网络中一定只有一条关键路径。（×）2.图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（）3.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。（）4.对于AOE网络，加速任一关键活动就能使整个工程提前完成。（×）5.如果有向图中各个顶点的度都大于2，则该图中必有回路。（×

39、）6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（×）7.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。（）8.对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。（）9.无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。（）10.对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（）11.若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（×）12.具有n个顶点的

40、连通图的生成树具有n-1条边（） 13在n个结点的无向图中,若边数>n-1,则该图必是连通图.(×)14.若一个有向图的邻接矩阵中对角线以下元素均为零,则该图的拓扑有序序列必定存在（）二、 二、填空题1. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_ n2_。2. 有一个n个顶点的有向完全图的弧数_ n(n-1)_。3. 在无向图中，若从顶点A到顶点B存在_路径_，则称A与B之间是连通的。4. 在一个无向图中，所有顶点的度数之和等于所有边数的_2_倍。三、 选择题1.顶点个数为n的无向图最多有_B_条边。A. n-1 B. n(n-1)/2 C. n(n+1)/

41、2 D. n(n-1)2.n个顶点的连通图至少有_A_条边。A. n-1 B. n C. n+1 D. 03.在一个有向图中，所有顶点的度数之和等于所有弧数的_B_倍。A. 3 B. 2 C. 1 D. 1/24.有向图的一个顶点的度为该顶点的_C_。A. 入度 B. 出度 C. 入度与出度之和 D. (入度出度)/25.一个连通图的生成树是包含图中所有顶点的一个_C_子图。A. 极小 B. 连通 C. 极小连通 D. 无环6.图的深度优先遍历类似于树的_A_。A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历7.下面关于图的存储的叙述中，哪一个是正确的。 _A_A.用邻接矩阵法存储图,占

42、用的存储空间数只与图中结点个数有关,而与边数无关B.用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关8如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_D_A.有向完全图 B.连通图C.强连通图D.有向无环图9.具有e条边的有向图，它的逆邻接表中有_B_个弧结点。A. e-1 B. e C. 2(e-1) D. 2e10.具有e条边的无向图，它的邻接表中有_ D _个边结点。A. e-1 B. e C. 2(e-1) D.

43、2e11.在一个图中，所有顶点的度数之和等于图的边数的_C_倍。A1/2 B. 1 C. 2 D. 412. 用邻接表表示图进行广度优先遍历时，通常是采用 B 来实现算法的。A栈 B. 队列 C. 树 D. 图排序和查找一、判断题1. 进行折半查找的表必须是顺序存储的有序表。（ ）2. 在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。（×）3. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。（）4. 直接选择排序是一种稳定的排序方法。（×）5. 堆排序是一种稳定的排序算法。(

44、5;)6. 快速排序法是一种稳定性排序法。（×）7. 散列法存储的基本思想是由关键字的值决定数据的存储地址（）8. 对n个元素的表用堆排序法进行排序，时间复杂度是O(log2n)（×）9. 在采用线性探测法处理冲突的散列表中,所有同义词在表中一定相邻（×）。10. 堆排序是所需辅助空间最少的排序。（）11. 一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（）二、填空题13. 若要对某二叉排序树进行遍历，保证输出元素的值序列按增序排列，应对该二叉排序树采用_遍历法。中序14. 元素关键字转换为该元素存储位置的函数f称为_。哈希函数

45、15. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。16. 假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。解：显然，平均查找长度O（log2n）<5次（25）。但具体是多少次，则不应当按照公式来计算（即（21×log221）/204.6次并不正确！）。因为这是在假设n2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为（12×24×38×45×5）74； ASL74/20

46、=3.7 ！17. 将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序。18. 先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体进行一次直接插入排序，此种排序方法叫做_希尔排序_排序。19. 每次使两个相邻的有序表合并成一个有序表的排序方法叫做_归并_排序。20. 每次从无序表中挑选出一个最大或最小元素，把它交换到有序表的一端，此种排序方法叫做_简单选择_排序。21. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_直接插入_排序。22. 每次直接或通过“枢轴”元素间接比较两个元素，若出现逆序排列时就交

47、换它们的位置，此种排序方法叫做_快速_排序。23. 假定一组数据的关键字为46,79,56,38,40,84，则利用堆排序方法建立的初始小顶堆为_38，40，56，79，46，84_。24. 假定一组数据的关键字为46,79,56,38,40,84，则以第一个记录为枢轴，对其进行第一趟快速排序的结果为_40,38,46,56,79,84_。25. 若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=keyMOD9，与18发生冲突的元素有_9_三、选择题（共20分，每题2分）1. 对于顺序存储的有序表(5, 12, 20, 26, 37, 42, 46, 50,

48、64)，哨兵位在前，为查找元素26，若采用顺序查找，需要比较_D_次才能查找成功。A. 3 B. 4 C. 5 D. 62. 设哈希表长为14，哈希函数f（k）=k11，已知表中已有4个元素，关键字分别为15，38，61，84，存储位置分别为4，5，6，7，其它存储位置为空，如用二次探测再散列处理冲突，关键字为49的存储位置是_D_。A. 8 B. 3 C. 5 D. 93. 对于顺序存储的有序表(5, 12, 20, 26, 37, 42, 46, 50, 64)，为查找元素26，若采用折半查找，需要比较_B_次才能查找成功。A. 3 B. 4 C. 5 D. 64. 对线性表进行折半查找时，要求线性表必须_C_。A. 以顺序方式存储B. 以链接方式存储C. 以顺序方式存储，且元素按关键字有序排序D. 以链接方式存储，且元素按关键字有序排序5. 对于哈希函数H(key)=key%13，被称为同义词的关键字是_D_A35和41 B.23和39C.15和44 D.25和516. 适于对动态查找表进行高效率查找的组织结构是_C_。A. 有序表 B. 顺序表 C. 二叉排序树 D. 链表7. 设哈希表长为14，哈希函数f（