大工21秋《数据结构》在线作业123辅导答案.docx

1、1.1.线性表采用顺序存储结构时，其地址线性表采用顺序存储结构时，其地址 ( ( ) )。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以【参考答案】: A2.2.队列操作的原则是队列操作的原则是( ( ) )。A.先进先出B.后进先出C.只能插入D.只能删除【参考答案】: A3.3.下述哪一条是顺序存储结构的优点下述哪一条是顺序存储结构的优点( ( ) )。A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示【参考答案】: A4.4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行若某线性表最常用的操作是存取任一指定序号的

2、元素和在最后进行插入和删除运算插入和删除运算, ,则利用则利用( ( ) )存储方式最节省时间。存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表【参考答案】: A5.5.链表不具有的特点是链表不具有的特点是( ( ) )。A.插入、 删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比【参考答案】: B6.6.一个栈的输入序列为一个栈的输入序列为 123123n n，若输出序列的第一个元素是若输出序列的第一个元素是 n n，输出输出第第i i（1=i=n1=i=n）个元素是）个元素是( ( ) )。A.不确定B.n-i1C.

3、iD.n-i【参考答案】: B7.7.设有三个元素设有三个元素 X,Y,ZX,Y,Z 顺序进栈顺序进栈( (进的过程中允许出栈进的过程中允许出栈),),下列得不到的下列得不到的出栈排列是出栈排列是( ( ) )。A.XYZB.YZXC.ZXYD.ZYX【参考答案】: C8.8.一个递归算法必须包括一个递归算法必须包括( ( ) )。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分【参考答案】: B9.9.设计一个判别表达式中左右括号是否配对出现的算法设计一个判别表达式中左右括号是否配对出现的算法, ,采用采用( ( ) )数据数据结构最佳。结构最佳。A.线性表的顺序存储结构

4、B.队列C.线性表的链式存储结构D.栈【参考答案】: D10.10.对稀疏矩阵进行压缩存储目的是对稀疏矩阵进行压缩存储目的是( ( ) )。A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度【参考答案】: C11.11.数据是对客观事物的符号表示数据是对客观事物的符号表示, ,在计算机科学中是指所有能输入到在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。计算机中并被计算机程序处理的符号的总称。T.对F.错【参考答案】: T12.12.算法的有穷性是指一个算法必须总是算法的有穷性是指一个算法必须总是( (对任何合法的输入对任何合法的输入) )在执

5、行有在执行有穷步之后结束穷步之后结束, ,且每一步都可在有穷时间内完成。且每一步都可在有穷时间内完成。T.对F.错【参考答案】: T13.13.算法的确定性是指算法中每一条指令必须有确切的含义算法的确定性是指算法中每一条指令必须有确切的含义, ,确保不会确保不会产生二义性。并且产生二义性。并且, ,在任何条件下在任何条件下, ,算法只有唯一的一条执行路径算法只有唯一的一条执行路径, ,即对即对于相同的输入只能得出相同的输出。于相同的输入只能得出相同的输出。T.对F.错【参考答案】: T14.14.一个算法是可行的一个算法是可行的, ,即算法中描述的操作都是可以通过已实现的基即算法中描述的操作都

6、是可以通过已实现的基本运算执行有限次来实现的。本运算执行有限次来实现的。T.对F.错【参考答案】: T15.15.栈是限定仅在表尾进行插入或删除操作的线性表。栈是限定仅在表尾进行插入或删除操作的线性表。T.对F.错【参考答案】: T16.16.队列是只允许在表的一端进行插入队列是只允许在表的一端进行插入, ,而在另一端删除元素的线性表而在另一端删除元素的线性表。T.对F.错【参考答案】: T17.17.线性表的主要存储结构有顺序存储结构和链式存储结构两种。线性表的主要存储结构有顺序存储结构和链式存储结构两种。T.对F.错【参考答案】: T18.18.算法的时间复杂度不仅仅依赖于问题的规模算法的

7、时间复杂度不仅仅依赖于问题的规模, ,也取决于输入实例的也取决于输入实例的初始状态。初始状态。T.对F.错【参考答案】: T19.19.顺序存储方法顺序存储方法, ,它不要求逻辑上相邻的结点在物理位置上亦相邻它不要求逻辑上相邻的结点在物理位置上亦相邻, ,结结点之间的逻辑关系是由附加的指针字段表示的。点之间的逻辑关系是由附加的指针字段表示的。T.对F.错【参考答案】: F20.20.链式存储方法链式存储方法, ,它是把逻辑上相邻的结点存储在物理位置相邻的存它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里储单元里, ,结点的逻辑关系由存储单元的邻接关系来体现。结点的逻辑关系由存储单元的邻接关

8、系来体现。T.对F.错【参考答案】: F1.1.若一棵二叉树具有若一棵二叉树具有 1010 个度为个度为 2 2 的结点的结点,5,5 个度为个度为 1 1 的结点的结点, ,则度为则度为 0 0的结点个数是的结点个数是( ( ) )。A.9B.11C.15D.不确定【参考答案】: B2.2.具有具有 1010 个叶结点的二叉树中有个叶结点的二叉树中有( ( ) )个度为个度为 2 2 的结点。的结点。A.8B.9C.10D.11【参考答案】: B3.3.设无向图的顶点个数为设无向图的顶点个数为 n,n,则该图最多有则该图最多有( ( ) )条边。条边。A.n-1B.n(n-1)/2C.n(n

9、1)/2D.0【参考答案】: B4.4.一个一个 n n 个顶点的连通无向图个顶点的连通无向图, ,其边的个数至少为其边的个数至少为( ( ) )。A.n-1B.nC.n1D.nlogn【参考答案】: A5.n5.n 个结点的完全有向图含有边的数目个结点的完全有向图含有边的数目( ( ) )。A.n*nB.n（n1)C.n2D.n*（nl）【参考答案】: D6.6.设有两个设有两个串串 p p 和和 q,q,其其中中 q q 是是 p p 的子串的子串, ,求求 q q 在在 p p 中首次出现的位置的中首次出现的位置的算法称为算法称为( ( ) )。A.求子串B.联接C.模式匹配D.求串长【

10、参考答案】: C7.7.串的长度是指串的长度是指( ( ) )。A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数【参考答案】: B8.8.树的后根遍历序列等同于该树对应的二叉树的树的后根遍历序列等同于该树对应的二叉树的( ( ) )。A.先序序列B.中序序列C.后序序列D.以上都不对【参考答案】: B9.9.在下列存储形式中在下列存储形式中, ,哪一个不是树的存储形式哪一个不是树的存储形式?(?( ) )A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法【参考答案】: D10.10.已知一棵二叉树的前序遍历结果为已知一棵二

11、叉树的前序遍历结果为 ABCDEF,ABCDEF,中序遍历结果为中序遍历结果为 CBAEDF,CBAEDF,则后序遍历的结果为则后序遍历的结果为( ( ) )。A.CBEFDAB.FEDCBAC.CBEDFAD.不定【参考答案】: A11.11.完全二叉树一定存在度为完全二叉树一定存在度为 1 1 的结点。的结点。T.对F.错【参考答案】: B12.12.二叉树的遍历结果不是唯一的二叉树的遍历结果不是唯一的. .T.对F.错【参考答案】: A13.13.一个树的叶结点一个树的叶结点, ,在前序遍历和后序遍历下在前序遍历和后序遍历下, ,皆以相同的相对位置出皆以相同的相对位置出现。现。T.对F.

12、错【参考答案】: T14.14.完全二叉树中完全二叉树中, ,若一个结点没有左孩子若一个结点没有左孩子, ,则它必是树叶。则它必是树叶。T.对F.错【参考答案】: T15.15.在在 n n 个结点的无向图中个结点的无向图中, ,若边数大于若边数大于 n-1,n-1,则该图必是连通图。则该图必是连通图。T.对F.错【参考答案】: F16.16.强连通图的各顶点间均可达。强连通图的各顶点间均可达。T.对F.错【参考答案】: T17.17.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。T.对F.错【参考答案】: F18.18.有向图

13、的邻接矩阵是对称的。有向图的邻接矩阵是对称的。T.对F.错【参考答案】: F19.19.无向图的邻接矩阵一定是对称矩阵无向图的邻接矩阵一定是对称矩阵, ,有向图的邻接矩阵一定是非对有向图的邻接矩阵一定是非对称矩阵。称矩阵。T.对F.错【参考答案】: F20.20.有有 n n 个顶点的无向图个顶点的无向图, , 采用邻接矩阵表示采用邻接矩阵表示, , 图中的边数等于邻接矩图中的边数等于邻接矩阵中非零元素之和的一半。阵中非零元素之和的一半。T.对F.错【参考答案】: T1.1.对线性表进行二分查找时对线性表进行二分查找时, ,要求线性表必须要求线性表必须( ( ) )。A.以顺序方式存储B.以顺

14、序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序【参考答案】: B2.2.散列表的地址区间为散列表的地址区间为 0-17,0-17,散列函数为散列函数为 H(K)=KH(K)=K modmod 1717。采用线性探。采用线性探测法处理冲突测法处理冲突, ,并将关键字序列并将关键字序列 26,25,72,38,8,18,5926,25,72,38,8,18,59 依次存储到散列依次存储到散列表中。元素表中。元素 5959 存放在散列表中的地址是存放在散列表中的地址是( ( ) )。A.8B.9C.10D.11【参考答案】: D3.3.下面给出的四种排序法中下面给出的

15、四种排序法中( ( ) )排序法是不稳定性排序法。排序法是不稳定性排序法。A.直接插入排序B.冒泡排序C.二路归并排序D.堆排序【参考答案】: D4.4.下列排序方法中下列排序方法中, ,哪一个是稳定的排序方法哪一个是稳定的排序方法?(?( ) )A.直接选择排序B.二分法插入排序C.希尔排序D.快速排序【参考答案】: B5.5.下面给出的四种排序方法中下面给出的四种排序方法中, ,排序过程中的比较次数与排序方法无关排序过程中的比较次数与排序方法无关的是的是( ( ) )。A.选择排序法B.插入排序法C.快速排序法D.堆排序法【参考答案】: A6.6.在下面的排序方法中在下面的排序方法中, ,

16、辅助空间为辅助空间为 O(n)O(n)的是的是( ( ) ) 。A.希尔排序B.堆排序C.选择排序D.归并排序【参考答案】: D7.7.下列排序算法中下列排序算法中, ,在待排序数据已有序时在待排序数据已有序时, ,花费时间反而最多的是花费时间反而最多的是( ( ) )排序。排序。A.冒泡B.希尔C.快速D.堆【参考答案】: C8.8.在排序算法中在排序算法中, ,每次从未排序的记录中挑出最小每次从未排序的记录中挑出最小( (或最大或最大) )关键码字的关键码字的记录记录, ,加入到已排序记录的末尾加入到已排序记录的末尾, ,该排序方法是该排序方法是( ( ) )。A.选择B.冒泡C.插入D.

17、堆【参考答案】: A9.9.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址址, ,因为散列函数是一对一的关系因为散列函数是一对一的关系, ,则选择好的则选择好的( ( ) )方法是散列文件的关方法是散列文件的关键。键。A.散列函数B.除余法中的质数C.冲突处理D.散列函数和冲突处理【参考答案】: D10.10.下述文件中适合于磁带存储的是下述文件中适合于磁带存储的是( ( ) )。A.顺序文件B.索引文件C.散列文件D.多关键字文件【参考答案】: A11.11.文件是记录的集合文件是记录的集合, ,每个记录由一个或多个数据

18、项组成每个记录由一个或多个数据项组成, ,因而一个文因而一个文件可看作由多个记录组成的数据结构。件可看作由多个记录组成的数据结构。T.对F.错【参考答案】: T12.12.散列函数越复杂越好散列函数越复杂越好, ,因为这样随机性好因为这样随机性好, ,冲突概率小冲突概率小. .T.对F.错【参考答案】: F13.13.负载因子负载因子 ( (装填因子装填因子) )是散列表的一个重要参数是散列表的一个重要参数, ,它反映散列表的装它反映散列表的装满程度。满程度。T.对F.错【参考答案】: T14.14.顺序查找法适用于存储结构为顺序或链接存储的线性表。顺序查找法适用于存储结构为顺序或链接存储的线

19、性表。T.对F.错【参考答案】: T15.15.对无序表用二分法查找比顺序查找快。对无序表用二分法查找比顺序查找快。T.对F.错【参考答案】: F16.16.排序的稳定性是指排序算法中的比较次数保持不变排序的稳定性是指排序算法中的比较次数保持不变, ,且算法能够终且算法能够终止。止。T.对F.错【参考答案】: F17.17.在执行某个排序算法过程中在执行某个排序算法过程中, ,出现了排序码朝着最终排序序列位置出现了排序码朝着最终排序序列位置相反方向移动相反方向移动, ,则该算法是不稳定的。则该算法是不稳定的。T.对F.错【参考答案】: F18.18.直接选择排序方法是稳定的。直接选择排序方法是稳定的。T.对F.错【参考答案】: F19.19.堆是满二叉树。堆是满二叉树。T.对F.错【参考答案】: F20.20.在待排数据基本有序的情况下在待排数据基本有序的情况下, ,快速排序效果最好。快速排序效果最好。T.对F.错【参考答案】: F