第3章 数据结构 答案
- 格式：doc
- 大小：85.00 KB
- 文档页数：14
第3章数据结构一、选择题1. 图形结构是数据元素之间存在一种____B_____。
A 一对多关系B 多对多关系C 多对一关系D 一对一关系2.算法分析的目的是___C_____。
A 找出数据结构的合理性B 研究算法中的输入和输出的关系C 分析算法的效率以求改进D 分析算法的易懂性和文档性3.算法的时间复杂度与___A____ 有关。
A 问题规模B 计算机硬件性能C 程序设计语言的类型或版本D 算法设计者的水平4.有下面的算法段：for (i=0; i<n; i++)k++;其时间复杂度为 B 。
A．O(1) B．O(n) C．O(log2n) D．O(n2)5.计算机算法必须具备输入、输出和___C____。
A、计算方法B、排序方法C、解决问题的有限运算步骤D、程序设计法6.____B___是数据的基本单位。
A、数据结构B、数据元素C、数据项D、数据类型7.下面，对非空线性表特点的论述，___C____是正确的。
A．所有结点有且只有一个直接前驱B．所有结点有且只有一个直接后继C．每个结点至多只有一个直接前驱，至多只有一个直接后继D．结点间是按照1对多的邻接关系来维系其逻辑关系的8.在顺序表中，只要知道____D____，就可以在相同的时间内求出任一结点的存储地址。
A、开始结点B、终端结点C、向量大小D、基地址和结点大小9.在非空线性表中，有且只有一个直接前驱和一个直接后继的结点是__C____。
A、开始结点B、终端结点C、内部结点D、所有结点10.顺序表中逻辑上相邻的结点的物理位置为_____A___。
A、一定相邻B、不必相邻C、按某种规律排列D、不要求11.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____B___。
A 110B 108C 100D 12012.链表不具有的特点是____A___。
A、可以随机访问任何一个元素B、插入和删除元素不需要移动元素C、不必事先估计存储空间D、所需的存储空间和链表长度无关13.数据结构反映了数据元素之间的结构关系。
链表是一种___D____。
A 顺序存储线性表B 非顺序存储非线性表C 顺序存储非线性表D 非顺序存储线性表14.链接存储的存储结构所占存储空间____A___A 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B 只有一部分，存放结点值C 只有一部分，存储表示结点间关系的指针D 分两部分，一部分存放结点值，另一部分存放结点所占单元数15.线性表Ｌ在____B____ 情况下适用于使用链式结构实现。
A 需经常修改Ｌ中的结点值B 需不断对Ｌ进行删除插入C Ｌ中含有大量的结点D Ｌ中结点结构复杂16.线性链表不具有的特点是____A__ 。
A 随机访问B 不必事先估计所需存储空间大小C 插入与删除时不必移动元素D 所需空间与线性表长度成正比17.在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动____B___个元素。
A．n-i B．n-i+1 C．n-i-1 D．i18.在长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要往前移动___A____个元素。
A．n-i B．n-i+1 C．n-i-1 D．i19.往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动____B___个结点。
A．n B．n/2 C．n+1 D．(n+1)/220.带表头结点的单链表Lk_h为空的判定条件是____B___。
A．Lk_h == NULL B．Lk_h->Next == NULLC．Lk_h->Next == Lk_h D．Lk_h != NULL21.在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。
现要在qtr 所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是__C____。
A．rtr->Next = ptr->Next; ptr->Next = rtr;B．ptr->Next = rtr->Next;C．qtr->Next = rtr; rtr->Next = ptr;D．ptr->Next = rtr; rtr->Next = qtr->Next;22.在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是___B_____。
A．qtr->Next = ptr ; B．qtr->Next = ptr->Next ;ptr->Next = qtr ; ptr->Next = qtr ;C．qtr->Next = ptr->Next ; D．ptr->Next = qtr ;ptr = qtr ; qtr->Next = ptr ;23.栈与一般线性表的区别在于___B_____。
A、数据元素的类型不同B、运算是否受限制C、数据元素的个数D、逻辑结构不同24.栈的插入和删除操作在___A___进行。
A、栈顶B、栈底C、任意位置D、指定位置25.一个顺序栈一旦被声明，其占用空间大小___A___。
A、已固定B、可以变化C、不能固定D、动态变化26.设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为____B_____A 2B 3C 4D 527.若让元素1，2，3依次进栈，则出栈次序不可能出现___C____种情况。
A 3，2，1B 2，1，3C 3，1，2D 1，3，228.一个栈的入栈序列是abcde，则栈不可能的输出序列是___C___。
A、edcbaB、decbaC、dceabD、abcde29.队列的插入操作是在____B_____进行的。
A、队首B、队尾C、队前D、队后30.队列的删除操作是在___A___进行的。
A、队首B、队尾C、队前D、队后31.为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。
主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是___A___。
A.队列B.栈C.线性表D.有序表32.下列关于线性表、栈和队列的叙述，错误的是___A___。
A.线性表是给定的n（n必须大于零）个元素组成的序列。
B.线性表允许在表的任何位置进行插入和删除操作。
C.栈只允许在一端进行插入和删除操作。
D.队列允许在一端进行插入，在令一端进行删除。
33.一个队列的入队序列是1,2,3,4，则队列的确定输出序列___B_____A.4,3,2,1B. 1,2,3,4C. 1,4,3,2D.3,2,4,134.若用一个大小为6的数组来实现循环队列,且当前rear 和front的值分别为0和3.当从队列中删除一个元素,再加入两个元素后, rear 和front的值分别为___B_____A.1和5B. 2和4C. 4和2D. 5和135.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是___B_____。
A.(rear+1)%n==frontB. rear==frontC. rear+1==frontD. (rear-l)%n==front36.循环队列存储在数组A[0..m]中，则入队时的操作为____D___。
A. rear=rear+1B. rear=(rear+1)%(m-1)B.rear=(rear+1)%m D. rear=(rear+1)%(m+1)37.数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为__D__A r－f;B （n＋f－r）% n;C n＋r－f;D （n＋r－f）% n38.一个长度为50的循环队列中，队头指针（front）等于41，队尾指针（rer）等于20，则队列中有___D____个元素。
A 41B 20C 21D 2939.二维数组M，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素____B____的起始地址相同。
A、M[2][4]B、M[3][4]C、M[3][5]D、M[4][4]40.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是__C___A、80B、100C、240D、27041.有一个二维数组[m][n]，按行存储，假设[0][0]存放位置在644（10进制），[2][2]存放位置在676（10进制），每个元素占一个空间，则[4][5]在__C___位置。
A 692B 626C 709D 72442.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为___C___。
A、SA+141B、SA+144C、SA+222D、SA+22543.在具有100个结点的树中，其边的数目为___C____。
A 101B 100C 99D 9844.按照树的定义，具有3个结点的树有___A___种形态。
A、2B、3C、4D、545.按照二叉树的定义，具有3个结点的二叉树有__D__种形态。
A、2B、3C、4D、546.下面说法中，__D__是正确的。
A、度为2的树是二叉树B、度为2的有序树是二叉树C、子树有严格左、右之分的树是二叉树D、子树有左、右之分、且度不超过2的树是二叉树47.下面的说法中，___C___是正确的。
A、二叉树的度为2B、二叉树中任意一个结点的度都为2C、任何二叉树中结点度可以小于2D、任何二叉树中至少有一个结点的度为248.若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数____B____。
A、9B、11C、12D、不确定49.具有10个叶结点的二叉树中有___A___个度为2的结点。
A、9B、11C、12D、不确定50.若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为____B____。
A、512B、1024C、2048D、409651.具有65个结点的完全二叉树的高度为____B______。
A 8B 7C 6D 552.深度为5的二叉树至多有____B_____个结点。
A、16B、31C、15D、3053.在一棵树的左孩子-右兄弟表示法中，一个结点的右孩子是该结点的___A____结点。
