77、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_____ _______。
78、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的____________遍历。 79、若图的邻接矩阵是对称矩阵，则该图一定是________________。
80、从如图所示的临接矩阵可以看出，该图共有______个顶点。如果是有向图，该图共有______条弧；如果是无向图，则共有________条边。
81、如果从一个顶点出发又回到该顶点，则此路径叫做___________。 82、一个具有个n顶点的无向图中，要连通全部顶点至少需要________条边。
83、给定序列{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它一定_________堆。
84、从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为_____________排序法。 85、折半搜索只适合用于___________________。
86、结点关键字转换为该结点存储单元地址的函数H称为_____________或叫__________。
87、在索引查找中，首先查找________，然后查找相应的_________，整个索引查找的平均查找长度等于查找索引表的平均长度与查找相应子表的平均查找长度的_______。 三、选择题：
（ ）1.数据结构通常是研究数据的 及它们之间的联系。 A存储和逻辑结构 B存储和抽象 C理想和抽象 D理想与逻辑 （ ）2.在堆栈中存取数据的原则是 。 A先进先出 B后进先出
C先进后出 D随意进出
（ ）3.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。 A.98 B.99 C.50 D.48
( )4.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( ) A.ABCDEF B.ABECDF C.CDFBEA D.CBDAEF
（ ）5.设有100个元素，用折半查找法进行查找时，最大比较次数是_____ 。 A.25 B.50 C.10 D.7
（ ）6.快速排序在_____情况下最易发挥其长处。
A.被排序数据中含有多个相同排序码 B.被排序数据已基本有序
C.被排序数据完全无序 D.被排序数据中最大值和最小值相差悬殊 （ ）7.由两个栈共享一个向量空间的好处是______。
A减少存取时间,降低下溢发生的机率 B节省存储空间,降低上溢发生的机率 C减少存取时间,降低上溢发生的机率 D节省存储空间,降低下溢发生的机率 （ ）8.某二叉树的前序和后序序列正好相反，则该二叉树一定是_____的二叉树 A空或者只有一个结点 B高度等于其结点数 C任一结点无左孩子 D任一结点无右孩子
（ ）9.设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：
r(15)=4; r(38)=5; r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是________。 A8 B3 C5 D9
（ ）10.在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为________。 A.e B.2e C.n2-e D.n2-2e
（ ）11.图的深度优先遍历类似于二叉树的_______。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历
（ ）12.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为_______。
A. O(1) B. O(log2n) C. O(n) D. O(n2)
（ ）13.堆的形状是一棵_______。 A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树
（ ）14.一个无向连连通图的生成树是含有该连通图的全部项点的_______。 A.极小连通子图 B.极小子图 C.极大连通子图 D.极大子图
（ ）15.一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用_______方法
A.快速排序 B.堆排序 C.插入排序 D.二路归并排序 （ ）16.设单链表中结点的结构为
typedef struct node { file://链表结点定义 ElemType data； file://数据
struct node * Link； file://结点后继指针 } ListNode；
已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作______。
A. s->link = p； p->link = s； B. s->link = p->link； p->link = s； C. s->link = p->link； p = s； D. p->link = s； s->link = p； （ ）17.设单链表中结点的结构为 typedef struct node { file://链表结点定义 ElemType data； file://数据
struct node * Link； file://结点后继指针 } ListNode；
非空的循环单链表first的尾结点（由p所指向）满足：______ A. p->link == NULL； B. p == NULL； C. p->link == first； D. p == first；
（ ）18.计算机识别、存储和加工处理的对象被统称为_________ A．数据 B.数据元素 C.数据结构 D.数据类型
（ ）19.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是________
A．O（1） B.O（n） C.O(nlogn) D.O(n2)
（ ）20．队和栈的主要区别是________ A.逻辑结构不同 B.存储结构不同
C.所包含的运算个数不同 D.限定插入和删除的位置不同 （ ）21．链栈与顺序栈相比，比较明显的优点是________ A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况
（ ）22．在目标串T[0…n-1]=”xwxxyxy”中，对模式串p[0…m-1]=”xy”进行子串定位操作的结果_______ A.0 B.2 C.3 D.5
（ ）23．已知广义表的表头为A，表尾为(B,C)，则此广义表为________ A.（A,(B,C)） B.（A,B,C） C.(A,B,C) D.(( A,B,C))
（ ）24．二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为_______