2024年数据结构在线测试章

《数据构造》第01章在线测试

《数据构造》第01章在线测试剩余時间：50:49

答題须知：1、本卷满分20分。

2、答完題後，請一定要單击下面的“交卷”按钮交卷，否则無法记录本试卷的成绩。

3、在交卷之前，不要刷新本网页，否则你的答題成果将會被清空。第一題、單项选择題（每題1分，5道題共5分）

1、计算机算法是指＿＿＿＿＿＿＿＿A、计算措施和运算成果B、调度措施C、处理某一問題的有限指令系列D、排序措施

2、算法分析的目的是＿＿＿＿＿＿＿＿A、找出数据构造的合理性B、分析算法的效率以求改善C、研究算法中输入和输出的关系D、分析算法的可讀性和可行性

3、设n為正整数。确定下面程序段的時间复杂度：k＝0;for(i＝1;i＜＝n;i++){for(j＝i;j＜＝n;j++)@k++;}A、nB、lognC、nlognD、n^2

4、树型构造和图构造都属于＿＿＿＿＿＿＿＿。A、线性构造B、非线性构造C、動态构造D、静态构造

5、下列函数中，時间复杂度最小的是＿＿＿＿＿＿＿＿。A、nlogn+5000nB、n^2-8000nC、n^logn-6000nD、10nlogn-7000n第二題、多选題（每題2分，5道題共10分）

1、根据元素之间关系的不一样特性，一般可有下列基本构造＿＿＿＿＿＿＿＿。A、集合B、线性构造C、树构造D、图构造

2、從逻辑上可以把数据构造分為＿＿＿＿＿＿＿＿。A、次序构造B、链式构造C、线性构造D、非线性构造E、動态构造F、静态构造

3、下列說法中，不對的的是＿＿＿＿＿＿＿＿。A、数据是数据元素的基本單位B、数据元素是数据中不可分割的最小標识單位C、数据元素可由若干個数据项构成D、数据项可由若干個数据元素构成

4、影响程序运行時间的原因包括＿＿＿＿＿＿＿＿＿＿＿＿＿＿。A、書写程序的語言B、問題的规模C、编译器产生的机器代码的质量D、计算机的运行速度E、算法的方略F、输出数据量

5、数据构造被形式化的定义為(D,S),其中D、S分别是＿＿＿＿＿＿＿＿的有限集合。A、数据元素B、数据操作C、数据存储D、数据关系第三題、判断題（每題1分，5道題共5分）

1、数据的物理构造是指数据和关系在计算机内的实际存储形式。對的錯误

2、算法原地工作的含义是指运行時不需要任何临時的辅助空间。對的錯误

3、数据對象是一组数据元素的集合。對的錯误

4、计算机算法必须具有的特性有：输入、输出、易讀性、稳定性和安全性。對的錯误

5、任何一种算法的设计取决于数据的逻辑构造，而算法的实現则依赖于所采用的存储构造。對的錯误测试成果如下：1.1[單项选择][對]计算机算法是指＿＿＿＿＿＿＿＿1.2[單项选择][對]算法分析的目的是＿＿＿＿＿＿＿＿1.3[單项选择][錯]设n為正整数。确定下面程序段的時间复杂度：k＝0;for(i＝1;i＜＝n;i++){for(j＝i;j＜＝n;j++)@k++;}1.4[單项选择][對]树型构造和图构造都属于＿＿＿＿＿＿＿＿。1.5[單项选择][對]下列函数中，時间复杂度最小的是＿＿＿＿＿＿＿＿。2.1[多选][對]根据元素之间关系的不一样特性，一般可有下列基本构造＿＿＿＿＿＿＿＿。2.2[多选][對]從逻辑上可以把数据构造分為＿＿＿＿＿＿＿＿。2.3[多选][對]下列說法中，不對的的是＿＿＿＿＿＿＿＿。2.4[多选][對]影响程序运行時间的原因包括＿＿＿＿＿＿＿＿＿＿＿＿＿＿。2.5[多选][對]数据构造被形式化的定义為(D,S),其中D、S分别是＿＿＿＿＿＿＿＿的有限集合。3.1[判断][對]数据的物理构造是指数据和关系在计算机内的实际存储形式。3.2[判断][對]算法原地工作的含义是指运行時不需要任何临時的辅助空间。3.3[判断][對]数据對象是一组数据元素的集合。3.4[判断][對]计算机算法必须具有的特性有：输入、输出、易讀性、稳定性和安全性。3.5[判断][對]任何一种算法的设计取决于数据的逻辑构造，而算法的实現则依赖于所采用的存储构造。《数据构造》第02章在线测试

《数据构造》第02章在线测试剩余時间：53:30第一題、單项选择題（每題1分，5道題共5分）

1、次序表中第一种元素的起始存储地址為100，每個元素的長度為4，则第五個元素的起始地址是＿＿＿＿＿＿＿。A、105B、116C、120D、124

2、若L是SqList类型的次序表，则线性表中的第i個元素是＿＿＿＿＿＿＿。A、L.elem[i]B、L.elem[i-1]C、L.elem[i+1]D、L.elem[i+2]

3、有頭結點的單链表（head為頭指针）是空表的条件是＿＿＿＿＿＿＿A、head-＞next＝＝NULL;B、head＝＝NULL;C、head-＞next＝＝head;D、head-＞next-＞next＝＝NULL;

4、非空的循环單链表(head為頭指针)的尾結點（由指针p所指示）应满足＿＿＿＿＿＿＿＿。A、p-＞next＝＝NULL;B、p＝＝NULL;C、p-＞next＝＝head;D、v

5、若在线性表的任何位置上删除元素的概率是相等的，那么在長度為n的次序表中删除一种元素時需平均移動＿＿＿＿＿＿＿＿個元素。A、nB、(n-1)/2C、n/2D、(n+1)/2第二題、多选題（每題2分，5道題共10分）

1、單链表的特點是＿＿＿＿＿＿＿＿。A、随机存取B、次序存取C、元素间的逻辑关系由指针指示D、插入删除元素時需要移動表中元素E、插入删除元素時不必移動元素，只须修改指针F、数据元素在存储器内的物理位置次序与它們的逻辑次序不一定相似

2、次序表的特點是＿＿＿＿＿＿＿＿。A、随机存取B、次序存取C、元素间的逻辑关系由指针指示D、插入删除元素時需要移動表中元素E、插入删除元素時不必移動元素，只须修改指针F、数据元素在存储器内的物理位置次序与它們的逻辑次序一定相似G、元素间的逻辑关系隐含在存储位置中

3、在双向循环链表中，若s是指向表中某結點的指针，则＿＿＿＿＿＿＿＿。A、s-＞next＝＝sB、s-＞next-＞prior＝＝sC、s-＞prior-＞next＝＝sD、s-＞prior＝＝s

4、次序表具有的特點有＿＿＿＿＿＿＿＿。A、随机存取B、次序存取C、插入删除需要移動元素D、事先估计存储空间的大小E、插入删除只需要修改指针

5、在双向循环链表（L為頭指针）中，指针p所指結點為尾結點的条件是＿＿＿＿＿＿＿＿。A、p==LB、p-＞next＝＝LC、L-＞prior＝＝pD、L-＞next＝＝p第三題、判断題（每題1分，5道題共5分）

1、次序表可以以元素在计算机内的物理位置的相邻性来表达线性表中元素之间的逻辑关系。對的錯误

2、在循环链表中设尾指针比设頭指针以便。（）對的錯误

3、线性表的次序存储构造优于链式存储构造。（）對的錯误

4、單链表的頭結點表达的是线性表中的第一种元素。對的錯误

5、在双向循环链表中插入或删除元素時仅需要修改結點的指针，不需要移動元素，因此算法的時间复杂度為O(1)。對的錯误测试成果如下：1.1[單项选择][對]次序表中第一种元素的起始存储地址為100，每個元素的長度為4，则第五個元素的起始地址是＿＿＿＿＿＿＿。1.2[單项选择][對]若L是SqList类型的次序表，则线性表中的第i個元素是＿＿＿＿＿＿＿。1.3[單项选择][對]有頭結點的單链表（head為頭指针）是空表的条件是＿＿＿＿＿＿＿1.4[單项选择][錯]非空的循环單链表(head為頭指针)的尾結點（由指针p所指示）应满足＿＿＿＿＿＿＿＿。1.5[單项选择][對]若在线性表的任何位置上删除元素的概率是相等的，那么在長度為n的次序表中删除一种元素時需平均移動＿＿＿＿＿＿＿＿個元素。2.1[多选][對]單链表的特點是＿＿＿＿＿＿＿＿。2.2[多选][對]次序表的特點是＿＿＿＿＿＿＿＿。2.3[多选][對]在双向循环链表中，若s是指向表中某結點的指针，则＿＿＿＿＿＿＿＿。2.4[多选][對]次序表具有的特點有＿＿＿＿＿＿＿＿。2.5[多选][對]在双向循环链表（L為頭指针）中，指针p所指結點為尾結點的条件是＿＿＿＿＿＿＿＿。3.1[判断][對]次序表可以以元素在计算机内的物理位置的相邻性来表达线性表中元素之间的逻辑关系。3.2[判断][對]在循环链表中设尾指针比设頭指针以便。（）3.3[判断][對]线性表的次序存储构造优于链式存储构造。（）3.4[判断][對]單链表的頭結點表达的是线性表中的第一种元素。3.5[判断][對]在双向循环链表中插入或删除元素時仅需要修改結點的指针，不需要移動元素，因此算法的時间复杂度為O(1)。《数据构造》第03章在线测试

《数据构造》第03章在线测试剩余時间：45:44第一題、單项选择題（每題1分，5道題共5分）

1、一种栈的入栈序列是1，2，3，…，n，其输出序列為p1,p2,p3,…pn,若p1＝n,则pi為＿＿＿＿＿＿＿＿。A、iB、n-iC、n-i+1D、不确定

2、在進行递归函数调用時，处理参数和返回地址需要使用一种称為＿＿＿＿＿＿＿＿的数据构造。A、线性表B、栈C、队列D、树

3、栈和队列的共同點是＿＿＿＿＿＿＿＿。A、都是後進先出B、都是先進先出C、都是只容許在端點处插入和删除元素D、無共同點

4、在次序栈中，base、top分别為栈底、栈顶指针，则＿＿＿＿＿＿＿時表明栈空。A、base＝＝NULLB、top＝＝NULLC、base＝＝topD、

5、非空次序栈中的栈顶指针一直指向栈顶元素的＿＿＿＿＿＿＿位置。A、上一种B、目前C、下一种D、第二題、多选題（每題2分，5道題共10分）

1、一种栈的入栈序列是{1,2,3,4,5},则栈也許的输出序列是＿＿＿＿＿＿＿。A、{1,2,3,4,5}B、{5,4,3,2,1}C、{2,1,4,3,5}D、{4,2,3,1,5}E、{5,1,4,3,2}F、{3,4,2,1,5}

2、循环队列中，设队列元素依次寄存在Q[0..m]中，f、r分别指示队頭元素位置和队尾元素的下一种位置，此時队空、队满的判断条件都是f＝＝r,為处理此矛盾，一般可采用＿＿＿＿＿＿＿。A、附设標志位，f＝＝r時借助標志判断B、牺牲一种元素空间，(r+1）％m＝＝f時队满，f＝＝r時队空C、牺牲一种元素空间，(r+1）％(m+1)＝＝f時队满，f＝＝r時队空D、另设表达队列長度的length域来区别队列空、满

3、下列数据构造中，＿＿＿＿＿＿＿是线性构造。A、线性表B、栈C、队列D、树E、图

4、队列操作的原则是＿＿＿＿＿＿＿。A、先進先出B、後進先出C、可以進行插入D、可以進行删除

5、一种队列的入队序列是{1,2,3,4},则队列不也許的输出序列是＿＿＿＿＿＿＿。A、4321B、1234C、1432D、3241第三題、判断題（每題1分，5道題共5分）

1、队列是先進先出的线性表。對的錯误

2、若顾客無法估计所用队列的最大長度，则最佳采用循环队列對的錯误

3、一种队列的入队序列是{1,2,3,4},则队列的输出序列只能是{1,2,3,4}。對的錯误

4、一种栈的入栈序列是{1,2,3,4,5},则{1,2,3,4,5}是不也許的输出序列。對的錯误

5、队列只能有一种输出序列，即队列中的元素只能按照進入队列的次序依次出队。對的錯误测试成果如下：1.1[單项选择][對]一种栈的入栈序列是1，2，3，…，n，其输出序列為p1,p2,p3,…pn,若p1＝n,则pi為＿＿＿＿＿＿＿＿。1.2[單项选择][對]在進行递归函数调用時，处理参数和返回地址需要使用一种称為＿＿＿＿＿＿＿＿的数据构造。1.3[單项选择][對]栈和队列的共同點是＿＿＿＿＿＿＿＿。1.4[單项选择][對]在次序栈中，base、top分别為栈底、栈顶指针，则＿＿＿＿＿＿＿時表明栈空。1.5[單项选择][對]非空次序栈中的栈顶指针一直指向栈顶元素的＿＿＿＿＿＿＿位置。2.1[多选][對]一种栈的入栈序列是{1,2,3,4,5},则栈也許的输出序列是＿＿＿＿＿＿＿。2.2[多选][對]循环队列中，设队列元素依次寄存在Q[0..m]中，f、r分别指示队頭元素位置和队尾元素的下一种位置，此時队空、队满的判断条件都是f＝＝r,為处理此矛盾，一般可采用＿＿＿＿＿＿＿。2.3[多选][對]下列数据构造中，＿＿＿＿＿＿＿是线性构造。2.4[多选][對]队列操作的原则是＿＿＿＿＿＿＿。2.5[多选][對]一种队列的入队序列是{1,2,3,4},则队列不也許的输出序列是＿＿＿＿＿＿＿。3.1[判断][對]队列是先進先出的线性表。3.2[判断][對]若顾客無法估计所用队列的最大長度，则最佳采用循环队列3.3[判断][對]一种队列的入队序列是{1,2,3,4},则队列的输出序列只能是{1,2,3,4}。3.4[判断][對]一种栈的入栈序列是{1,2,3,4,5},则{1,2,3,4,5}是不也許的输出序列。3.5[判断][對]队列只能有一种输出序列，即队列中的元素只能按照進入队列的次序依次出队。《数据构造》第04章在线测试第一題、單项选择題（每題1分，5道題共5分）

1、设有两個串s1和s2，求s2在s1中初次出現的位置的操作是＿＿＿＿＿＿＿＿。A、连接B、模式匹配C、求子串D、求串長

2、字符串是一种特殊的线性表，其特殊性在于它的数据元素只能是＿＿＿＿＿＿＿＿。A、字符B、字符串C、数字D、字母

3、串是一种特殊的线性表，其特殊性体目前＿＿＿＿＿＿＿＿。A、可以次序存储B、数据元素是一种字符C、可以链接存储D、数据元素可以是多种字符

4、空格串的長度為＿＿＿＿＿＿＿＿。A、0B、1C、串中空格的個数D、

5、设串s＝"Iamastudent.",则s的長度為＿＿＿＿＿＿＿＿。A、11B、12C、15D、16第二題、多选題（每題2分，5道題共10分）

1、在定長次序存储表达中，對串長的表达措施有＿＿＿＿＿＿＿＿＿＿。A、用域变量表达B、用下標為0的数组分量表达C、在串值後加結束標识字符D、無法明确表达

2、如下說法對的的是＿＿＿＿＿＿＿＿＿＿。A、串長相等的两個串相等B、串值的引号不被计算在串長之内C、空串的長度為0D、空格串的長度為0

3、如下有关串的存储方式的說法中對的的是＿＿＿＿＿＿＿＿＿＿。A、定長次序表达和堆分派表达都是串的次序存储表达B、定長次序表达的串的存储空间是编译時预先分派的一种比较大的持续空间C、堆分派表达的串的存储空间是在程序执行過程中動态分派的D、堆分派存储表达時的空串不占用持续的存储区

4、串的机内表达措施有＿＿＿＿＿＿＿＿＿＿。A、定長次序存储表达B、堆分派存储表达C、块链存储表达D、散列表达

5、串用定長次序存储方式表达時，有也許发生“截断”的操作有＿＿＿＿＿＿＿＿＿＿。A、串连接B、求子串C、串替代D、插入串E、删除子串第三題、判断題（每題1分，5道題共5分）

1、空串和空格串是同样的。對的錯误

2、假如一种串中的所有字符均在另一串中出現，则前者是後者的子串。對的錯误

3、串也有两种存储构造：次序构造和链式构造。對的錯误

4、在串的链式存储构造中，結點大小与存储密度之间没有关系。對的錯误

5、在C語言中，用動态分派函数進行管理的自由存储区称為“堆”。對的錯误测试成果如下：1.1[單项选择][對]设有两個串s1和s2，求s2在s1中初次出現的位置的操作是＿＿＿＿＿＿＿＿。1.2[單项选择][對]字符串是一种特殊的线性表，其特殊性在于它的数据元素只能是＿＿＿＿＿＿＿＿。1.3[單项选择][對]串是一种特殊的线性表，其特殊性体目前＿＿＿＿＿＿＿＿。1.4[單项选择][對]空格串的長度為＿＿＿＿＿＿＿＿。1.5[單项选择][對]设串s＝"Iamastudent.",则s的長度為＿＿＿＿＿＿＿＿。2.1[多选][對]在定長次序存储表达中，對串長的表达措施有＿＿＿＿＿＿＿＿＿＿。2.2[多选][對]如下說法對的的是＿＿＿＿＿＿＿＿＿＿。2.3[多选][錯]如下有关串的存储方式的說法中對的的是＿＿＿＿＿＿＿＿＿＿。ABC2.4[多选][對]串的机内表达措施有＿＿＿＿＿＿＿＿＿＿。2.5[多选][對]串用定長次序存储方式表达時，有也許发生“截断”的操作有＿＿＿＿＿＿＿＿＿＿。3.1[判断][對]空串和空格串是同样的。3.2[判断][對]假如一种串中的所有字符均在另一串中出現，则前者是後者的子串。3.3[判断][對]串也有两种存储构造：次序构造和链式构造。3.4[判断][對]在串的链式存储构造中，結點大小与存储密度之间没有关系。3.5[判断][對]在C語言中，用動态分派函数進行管理的自由存储区称為“堆”。《数据构造》第05章在线测试

《数据构造》第05章在线测试剩余時间：46:14

答題须知：1、本卷满分20分。

2、答完題後，請一定要單击下面的“交卷”按钮交卷，否则無法记录本试卷的成绩。

3、在交卷之前，不要刷新本网页，否则你的答題成果将會被清空。第一題、單项选择題（每題1分，5道題共5分）

1、深度為5的满二叉树有＿＿＿＿＿＿＿＿個結點。A、16B、32C、31D、10

2、在线索化二叉树中，t所指結點没有左子树的充要条件是＿＿＿＿＿＿＿＿。A、t-＞lchild＝＝NULLB、t-＞LTag＝＝1C、t-＞LTag＝＝1&&t-＞lchild＝＝NULLD、以上都不對

3、树最适合表达＿＿＿＿＿＿＿＿。A、有序数据元素B、無序数据元素C、元素之间具有分支层次关系的数据D、元素之间無联络的数据

4、具有100個結點的完全二叉树的深度為＿＿＿＿＿＿＿＿。A、6B、7C、8D、9

5、對于体現式(a-b+c)*d/(e+f),其前缀体現式為＿＿＿＿＿＿＿＿。A、/*+-abcd+efB、a-b+c*d/e+fC、/*-a+bcd+efD、ab-c+d*ef+/第二題、多选題（每題2分，5道題共10分）

1、下列有关完全二叉树的论述中，對的的有＿＿＿＿＿＿＿＿。A、完全二叉树一定是满二叉树B、满二叉树一定是完全二叉树C、完全二叉树中要么没有結點的度為1，要么只也許有一种結點的度為1D、只有一种結點的度為1的二叉树一定是完全二叉树

2、下列有关树和二叉树的论述中，對的的有＿＿＿＿＿＿＿＿。A、森林和二叉树之间可以互相转换B、树和二叉树之间可以互相转换C、二叉树的子树有左右之分，而树的子树没有左右之分D、二叉树結點的最大度数為2，而树的結點的最大度数没有限制

3、树可采用的存储构造有＿＿＿＿＿＿＿＿。A、次序构造B、多重链表C、二叉链表D、孩子链表

4、用二叉树的＿＿＿＿＿＿＿＿序列可唯一确实定一棵二叉树。A、先序和中序B、先序和後序C、後序和中序D、层序和中序

5、树可采用的存储构造有＿＿＿＿＿＿＿＿。A、次序构造B、多重链表C、二叉链表D、孩子链表第三題、判断題（每題1分，5道題共5分）

1、二叉树的先、中、後序遍历序列中，叶子結點的相對次序不會发生变化。對的錯误

2、将一棵树转换成對应的二叉树後，二叉树的根結點肯定没有左子树。對的錯误

3、用树的先序遍历和中序遍历序列可以导出树的後序遍历。對的錯误

4、在一棵非空二叉树的中序遍历序列中，根結點的右边只有其右子树上的所有結點。對的錯误

5、二叉树的先序遍历序列中，任意一种結點均处在其孩子結點的前面。對的錯误测试成果如下：1.1[單项选择][對]深度為5的满二叉树有＿＿＿＿＿＿＿＿個結點。1.2[單项选择][對]在线索化二叉树中，t所指結點没有左子树的充要条件是＿＿＿＿＿＿＿＿。1.3[單项选择][對]树最适合表达＿＿＿＿＿＿＿＿。1.4[單项选择][對]具有100個結點的完全二叉树的深度為＿＿＿＿＿＿＿＿。1.5[單项选择][錯]對于体現式(a-b+c)*d/(e+f),其前缀体現式為＿＿＿＿＿＿＿＿。2.1[多选][錯]下列有关完全二叉树的论述中，對的的有＿＿＿＿＿＿＿＿。2.2[多选][對]下列有关树和二叉树的论述中，對的的有＿＿＿＿＿＿＿＿。2.3[多选][對]树可采用的存储构造有＿＿＿＿＿＿＿＿。2.4[多选][對]用二叉树的＿＿＿＿＿＿＿＿序列可唯一确实定一棵二叉树。2.5[多选][對]树可采用的存储构造有＿＿＿＿＿＿＿＿。3.1[判断][對]二叉树的先、中、後序遍历序列中，叶子結點的相對次序不會发生变化。3.2[判断][對]将一棵树转换成對应的二叉树後，二叉树的根結點肯定没有左子树。3.3[判断][對]用树的先序遍历和中序遍历序列可以导出树的後序遍历。3.4[判断][錯]在一棵非空二叉树的中序遍历序列中，根結點的右边只有其右子树上的所有結點。3.5[判断][對]二叉树的先序遍历序列中，任意一种結點均处在其孩子結點的前面。《数据构造》第06章在线测试

《数据构造》第06章在线测试剩余時间：48:56

答題须知：1、本卷满分20分。

2、答完題後，請一定要單击下面的“交卷”按钮交卷，否则無法记录本试卷的成绩。

3、在交卷之前，不要刷新本网页，否则你的答題成果将會被清空。第一題、單项选择題（每題1分，5道題共5分）

1、一种有n個顶點的無向图若是连通图，则至少有＿＿＿＿＿＿＿＿条边。A、n-1B、nC、n+1D、(n+1)/2

2、無向图的邻接矩阵是一种＿＿＿＿＿＿＿＿。A、對称矩阵B、零矩阵C、對角矩阵D、上三角矩阵

3、图的深度优先遍历算法类似于二叉树的＿＿＿＿＿＿＿＿。A、先序遍历B、中序遍历C、後序遍历D、层序遍历

4、假如從無向图的任意顶點出发進行一次深度优先遍历就能访問到图中所有顶點，则该图一定是＿＿＿＿＿＿＿＿。A、完全图B、连通图C、有回路D、一棵树

5、對＿＿＿＿＿＿＿＿，用Prim算法求最小生成树较為合适。A、非连通图B、连通图C、稀疏图D、稠密图第二題、多选題（每題2分，5道題共10分）

1、假如對無向图G必须進行二次广度优先遍历才能访問到图中所有顶點，则下列說法中對的的是＿＿＿＿＿＿＿＿。A、G肯定不是完全图B、G肯定不是连通图C、G中一定有回路D、G有两個连通分量

2、在拓扑排序中，拓扑序列的第一种顶點一定是＿＿＿＿＿＿＿＿的顶點。A、入度為0B、没有前驱C、出度為0D、没有後继

3、對图分别進行深度优先遍历和广度优先遍历，得到的顶點访問序列＿＿＿＿＿＿＿＿。A、一定相似B、一定不一样C、不一定相似D、也許相似

4、下列有关最短途径的說法中，對的的有＿＿＿＿＿＿＿＿。A、Dijkstra算法是按途径長度递增的次序依次产生從某一固定源點到其他各顶點之间的最短途径。B、若仅求單一源點到某一特定顶點之间的最短途径，则其算法的時间复杂度可以到达O(n)。C、求图中每一對顶點间最短途径的Floyd算法的時间复杂度為O(n^3)。D、求图中每一對顶點间的最短途径也可用Dijkstra算法实現。

5、已知一种無向图的邻接矩阵表达，计算第i個顶點的度的措施是＿＿＿＿＿＿。A、计算邻接矩阵中第i行的元素之和B、计算邻接矩阵中第i列的元素之和C、计算邻接矩阵中第i行的非零元個数D、计算邻接矩阵中第i列的非零元個数第三題、判断題（每題1分，5道題共5分）

1、若從無向图的一种顶點出发進行广度优先遍历可访問到图中的所有顶點，则该图一定是连通图。對的錯误

2、在n個顶點的無向图中，若边数不小于n-1，则该图一定是连通图。對的錯误

3、對稀疏图，用Prim算法求最小生成树较為合适對的錯误

4、运用拓扑排序，可检测一种有向图中与否存在环對的錯误

5、若從無向图的一种顶點出发進行深度优先遍历可访問到图中的所有顶點，则该图一定是连通图。對的錯误测试成果如下：1.1[單项选择][對]一种有n個顶點的無向图若是连通图，则至少有＿＿＿＿＿＿＿＿条边。1.2[單项选择][對]無向图的邻接矩阵是一种＿＿＿＿＿＿＿＿。1.3[單项选择][對]图的深度优先遍历算法类似于二叉树的＿＿＿＿＿＿＿＿。1.4[單项选择][對]假如從無向图的任意顶點出发進行一次深度优先遍历就能访問到图中所有顶點，则该图一定是＿＿＿＿＿＿＿＿。1.5[單项选择][對]對＿＿＿＿＿＿＿＿，用Prim算法求最小生成树较為合适。2.1[多选][對]假如對無向图G必须進行二次广度优先遍历才能访問到图中所有顶點，则下列說法中對的的是＿＿＿＿＿＿＿＿。2.2[多选][對]在拓扑排序中，拓扑序列的第一种顶點一定是＿＿＿＿＿＿＿＿的顶點。2.3[多选][對]對图分别進行深度优先遍历和广度优先遍历，得到的顶點访問序列＿＿＿＿＿＿＿＿。2.4[多选][對]下列有关最短途径的說法中，對的的有＿＿＿＿＿＿＿＿。2.5[多选][對]已知一种無向图的邻接矩阵表达，计算第i個顶點的度的措施是＿＿＿＿＿＿。3.1[判断][對]若從無向图的一种顶點出发進行广度优先遍历可访問到图中的所有顶點，则该图一定是连通图。3.2[判断][對]在n個顶點的無向图中，若边数不小于n-1，则该图一定是连通图。3.3[判断][對]對稀疏图，用Prim算法求最小生成树较為合适3.4[判断][對]运用拓扑排序，可检测一种有向图中与否存在环3.5[判断][對]若從無向图的一种顶點出发進行深度优先遍历可访問到图中的所有顶點，则该图一定是连通图。《数据构造》第07章在线测试

《数据构造》第07章在线测试剩余時间：49:55

答題须知：1、本卷满分20分。

2、答完題後，請一定要單击下面的“交卷”按钮交卷，否则無法记录本试卷的成绩。

3、在交卷之前，不要刷新本网页，否则你的答題成果将會被清空。第一題、單项选择題（每題1分，5道題共5分）

1、＿＿＿＿＿＿＿二叉排序树可得到一种关键字的有序序列。A、先序遍历B、中序遍历C、後序遍D、层序遍历

2、用折半查找對長度為12的有序表進行查找，则等概率下查找成功時的平均查找長度為＿＿＿＿＿＿＿。A、35/12B、37/12C、39/12D、43/12

3、用链地址法处理冲突构造的散列表中，每個地址單元所链接的同义詞表的＿＿＿＿＿＿＿相似。A、关键字B、元素值C、散列地址D、含义

4、假如规定一种线性表既能较快的查找，又能适应動态变化的规定，可以采用＿＿＿＿＿＿＿查找措施。A、折半B、次序C、分块D、散列

5、高度為5的二叉平衡树至少有＿＿＿＿＿＿＿個結點。A、10B、12C、15D、17第二題、多选題（每題2分，5道題共10分）

1、平衡二叉树上結點的平衡因子可认為＿＿＿＿＿＿＿。A、-2B、-1C、0D、1E、2

2、构造散列函数時一般考虑的原因有＿＿＿＿＿＿＿。A、计算函数的工作量B、关键字的長度C、散列表長D、关键字的分布状况

3、构造散列表時处理冲突常用的措施有＿＿＿＿＿＿＿。A、链地址法B、数字分析法C、開放定址法D、平方取中法E、再哈希法F、求余法G、建立公共溢出区

4、對于10個元素的有序表進行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿＿＿＿＿＿。A、1B、2C、3D、4E、6F、7G、8H、9

5、在次序表的次序查找算法中，监视哨的位置＿＿＿＿＿＿＿。A、只能在表頭B、只能在表尾C、可以在表頭D、可以在表尾第三題、判断題（每題1分，5道題共5分）

1、折半查找和二叉排序树查找的時间性能相似。對的錯误

2、在散列函数H(key)＝keymodp中，函数的好壞与p的选择没有任何关系。對的錯误

3、平衡二叉树是指左、右子树的高度差的绝對值不不小于1的二叉树。對的錯误

4、在分块查找中，對索引表的查找既可用次序查找法，也可用折半查找法。對的錯误

5、若散列表的装填因子不不小于1，则可防止冲突的产生對的錯误测试成果如下：1.1[單项选择][對]＿＿＿＿＿＿＿二叉排序树可得到一种关键字的有序序列。1.2[單项选择][對]用折半查找對長度為12的有序表進行查找，则等概率下查找成功時的平均查找長度為＿＿＿＿＿＿＿。1.3[單项选择][對]用链地址法处理冲突构造的散列表中，每個地址單元所链接的同义詞表的＿＿＿＿＿＿＿相似。1.4[單项选择][對]假如规定一种线性表既能较快的查找，又能适应動态变化的规定，可以采用＿＿＿＿＿＿＿查找措施。1.5[單项选择][對]高度為5的二叉平衡树至少有＿＿＿＿＿＿＿個結點。2.1[多选][對]平衡二叉树上結點的平衡因子可认為＿＿＿＿＿＿＿。2.2[多选][對]构造散列函数時一般考虑的原因有＿＿＿＿＿＿＿。2.3[多选][對]构造散列表時处理冲突常用的措施有＿＿＿＿＿＿＿。2.4[多选][對]對于10個元素的有序表進行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿＿＿＿＿＿。2.5[多选][對]在次序表的次序查找算法中，监视哨的位置＿＿＿＿＿＿＿。3.1[判断][對]折半查找和二叉排序树查找的時间性能相似。3.2[判断][對]在散列函数H(key)＝keymodp中，函数的好壞与p的选择没有任何关系。3.3[判断][對]平衡二叉树是指左、右子树的高度差的绝對值不不小于1的二叉树。3.4[判断][對]在分块查找中，對索引表的查找既可用次序查找法，也可用折半查找法。3.5[判断][對]若散列表的装填因子不不小于1，则可防止冲突的产生《数据构造》第08章在线测试

《数据构造》第08章在线测试剩余時间：56:05

答題须知：1、本卷满分20分。

2、答完題後，請一定要單击下面的“交卷”按钮交卷，否则無法记录本试卷的成绩。

3、在交卷之前，不要刷新本网页，否则你的答題成果将會被清空。第一題、單项选择題（每題1分，5道題共5分）

1、下列措施中，＿＿＿＿＿＿＿＿是稳定的排序措施。A、折半插入排序B、希尔排序C、迅速排序D、堆排序

2、在待排序的元素序列基本有序的前提下，效率最高的排序措施是＿＿＿＿＿＿＿。A、直接插入排序B、起泡排序C、迅速排序D、堆排序

3、一组记录的关键字序列為{46，79，56，38，40，84}，则运用迅速排序措施，以第一种记录為枢轴得到的一次划提成果是＿＿＿＿＿＿＿。A、{38，40，46，56，79，84}B、{40，38，46，79，56，84}C、{40，38，46，56，79，84}D、{40，38，46，84，56，79}

4、在下列排序措施中，平均状况下占用内存量最大的是＿＿＿＿＿＿＿措施。A、迅