当前位置: 首页 > >

数据结构C语言版期末考试试题(附带复*资料)

“数据结构”期末考试试题 一、单选题(每小题 2 分,共 12 分) 1. 在一个单链表 HL 中, 若要向表头插入一个由指针 p 指向的结点, 则执行( )。 A. HL=ps p 一>next=HL B. p 一>next=HL;HL=p3 C. p 一>next=Hl;p=HL; D. p 一>next=HL 一>next;HL 一>next=p; 2.n 个顶点的强连通图中至少含有( )。 A.n—l 条有向边 B.n 条有向边 C.n(n—1)/2 条有向边 D.n(n 一 1)条有向边 3.从一棵二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4.由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径 长度为( )。 A.24 B.48 C. 72 D. 53 5.当一个作为实际传递的对象占用的存储空间较大并可能需要修改时,应最好 把它说明为( )参数,以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6.向一个长度为 n 的顺序表中插人一个新元素的*均时间复杂度为( )。 A.O(n) B.O(1) C.O(n2) D.O(10g2n) 二、填空题(每空 1 分,共 28 分) 1.数据的存储结构被分为——、——、——和——四种。 2.在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同,各自 分别为——域和——域。 3.——中缀表达式 3 十 x*(2.4/5—6)所对应的后缀表达式为————。 4.在一棵高度为 h 的 3 叉树中,最多含有——结点。 5.假定一棵二叉树的结点数为 18,则它的最小深度为——,最大深度为——· 6. 在一棵二叉搜索树中, 每个分支结点的左子树上所有结点的值一定——该结 点的值,右子树上所有结点的值一定——该结点的值。 7.当向一个小根堆插入一个具有最小值的元素时,该元素需要逐层——调整, 直到被调整到——位置为止。 8.表示图的三种存储结构为——、——和———。 9. 对用邻接矩阵表示的具有 n 个顶点和 e 条边的图进行任一种遍历时, 其时间 复杂度为——, 对用邻接表表示的图进行任一种遍历时, 其时间复杂度为——。 10.从有序表(12,18,30,43,56,78,82,95)中依次二分查找 43 和 56 元素 时,其查找长度分别为——和——· 11. 假定对长度 n=144 的线性表进行索引顺序查找, 并假定每个子表的长度均

为 ,则进行索引顺序查找的*均查找长度为——,时间复杂度为——· 12.一棵 B—树中的所有叶子结点均处在——上。 13.每次从无序表中顺序取出一个元素,把这插入到有序表中的适当位置,此 种排序方法叫做——排序;每次从无序表中挑选出一个最小或最大元素, 把它交换到有序表的一端,此种排序方法叫做——排序。 14. 快速排序在乎均情况下的时间复杂度为——, 最坏情况下的时间复杂度为——。 三、运算题(每小题 6 分,共 24 分) 1.假定一棵二叉树广义表表示为 a(b(c,d),c(((,8))),分别写出对它进行 先序、中序、后序和后序遍历的结果。 先序: 中序; 后序: 2.已知一个带权图的顶点集 V 和边集 G 分别为: V={0,1,2,3,4,5}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9, (4,5)10}, 则求出该图的最小生成树的权。 最小生成树的权; 3.假定一组记录的排序码为(46,79,56,38,40,84,50,42),则利用堆排 序方法建立的初始堆为——。 4.有 7 个带权结点,其权值分别为 3,7,8,2,6,10,14,试以它们为叶子 结点生成一棵哈夫曼树,求出该树的带权路径长度、高度、双分支结点数。 带权路径长度:—— 高度:—— 双分支结点数:——。 四、阅读算法,回答问题(每小题 8 分,共 16 分) 1.VOldAC(List&L) { InitList(L); InsertRear(L;25); InsertFront(L,50); IntaL4]={5,8,12,15,36}; for(inti=0; i<5; i++) if (a[i]%2==0)InsertFront(L,a[i]); elselnsertRear(L,a[i]); } 该算法被调用执行后,得到的线性表 L 为: 2.void AG(Queue&Q) { InitQueue(Q); inta[5]={6,12,5,15,8}; for(int i=0;i<5; i++)QInsert(Q,a[i]); QInsert(Q,QDelete(Q));

QInsert(Q,20); QInsert(Q,QDelete(Q)十 16); while(!QueueEmpty(Q))cout<<QDelete(Q)<<” ; } 该算法被调用后得到的输出结果为: 五、算法填空,在画有横线的地方填写合适的内容(每小题 6 分,共 12 分) 1.从一维数组 A[n)中二分查找关键字为 K 的元素的递归算法,若查找成功则 返回对应元素的下标,否则返回一 1。 IntBinsch(ElemTypeA[],Intlow,int high,KeyTypeK) { if(low<=high) { int mid=(low+high)/2; if(K==A[mid].key)——; else if (K<A[mid].key)——; else ; } else return—l; } 2.已知二叉树中的结点类型 BinTreeNode 定义为: structBinTreeNode{ElemType data;BinTreeNode*left,*right}; 其中 data 为结点值域,left 和 right 分别为指向左、右子女结点的指针域。 下面函数的功能是返回二叉树 BT 中值为 x 的结点所在的层号, 请在划有横线的 地方填写合适内容。 Int NodeLevel(BinTreeNode * BT,ElemType X) { if(BT:=NULL)return 0; //空树的层号为 0 else if(BT 一>data==X)return 1; //根结点的层号为 1 //向子树中查找 x 结点 else{ int cl=NodeLevel(BT 一>left,X); if(cl>=1)return cl+1; int c2= ; if——; //若树中不存在 X 结点则返回 o else return 0; } } 六、编写算法(8 分) 按所给函数声明编写一个算法, 从表头指针为 HL 的单链表中查找出具有最大值 的结点,该最大值由函数返回,若单链表为空则中止运行。

EIemType MaxValue(LNOde*HL);

“数据结构”期末考试试题答案 一、单选题(每小题 2 分,共 12 分) 评分标准;选对者得 2 分,否则不得分。 1.B 2.B 3.C 4.D 5.B 6.A 二、填空题(每空 1 分,共 28 分) 1.顺序结构 链接结构 索引结构 散列结构(次序无先后) 2.值(或 data) 子表指针(或 sublist) 3.3 x 2.4 5/6 一*十 4.(3h 一 1)/2 5. 5 18 6.小于 大于(或大于等于) 7.向上 堆顶 8.邻接矩阵 邻接表 边集数组(次序无先后) 2 9.O(n ) O(e) 10. 1 3 11.13 O( ) 12.同一层 13.插人 选择 14.O(nlog2n) O(n2) 三、运算题(每小题 6 分,共 24 分) 1.先序:a,b,c,d,e,f,e //2 分 中序:c,b,d,a,f,8,e //2 分 后序:c,d,b,e,f,e,a //2 分 2.最小生成树的权:31 //6 分 3.(84,79,56,42,40,46,50,38) //6 分 4.带权路径长度:131 //3 分 高度:5 //2 分 双分支结点数:6 //1 分 四、阅读算法,回答问题(每小题 8 分,共 16 分) 评分标准:每小题正确得 8 分,出现一处错误扣 4 分,两处及以上错误不得分。 1.(36,12,8,50,25,5,15) 2.5 15 8 6 20 28 五、算法填空,在画有横线的地方填写合适的内容(每小题 6 分,共 12 分) 1.feturn mid //2 分 returnBinsch(A,low,mid 一 1,K) //2 分 returnBmsch(A,mid+1,high,K) //2 分 2.NodeLevel(BT 一>right,X) //3 分

(c2>=1)returnc2 十 1 //3 分 六、编写算法(8 分) 评分标准:请参考语句后的注释,或根据情况酌情给分。 ElemType MaxValue(LNodeO* HL。) { if (HL==NUlL){ //2 分 cerr<<"Linked llst is empty!”<<endl; exit(1); } ElemTypemax:HL 一>data; //3 分 LNOde*p=HI 一>next; //4 分 while(P!:NULL){ //7 分 if(max<p 一>data)max=p 一>data; p=p 一>next; } returnmax; //8 分 }

数据结构复*资料

一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机 的 关系 和运算等的学科。 数据元素 的有限集合,R 操作对象

以及它们之间的

2. 数据结构被形式地定义为(D, R) ,其中 D 是 是 D 上的 关系 有限集合。 逻辑结构

3. 数据结构包括数据的 这三个方面的内容。

、数据的 存储结构

和数据的

运算

4. 数据结构按逻辑结构可分为两大类,它们分别是

线性结构



非线性结





5. 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系, 图形结构中元素之间存在多对多关系。 6. 在线性结构中,第一个结点 驱结点; 最后一个结点 没有 没有 前驱结点,其余每个结点有且只有 1 个前 后续结点, 其余每个结点有且只有 1 个后续结点。 结点,其余每个结点有且只有 1 个

7. 在树形结构中,树根结点没有 前驱 前驱结点;叶子结点没有 个 。 后续

结点,其余每个结点的后续结点数可以任意多

8. 在图形结构中,每个结点的前驱结点数和后续结点数可以

任意多个



9. 数据的存储结构可用四种基本的存储方法表示, 它们分别是顺序 引 和 散列 。

、 链式 、 索

10. 数据的运算最常用的有 5 种,它们分别是插入 、 删除、修改、 查找 、排序。 11. 一个算法的效率可分为 时间 效率和 空间 效率。

12. 在顺序表中插入或删除一个元素,需要*均移动 表中一半元素,具体移动的 元素个数与 表长和该元素在表中的位置 13. 线性表中结点的集合是 有限 有关。 一对一 的。

的,结点间的关系是

14. 向一个长度为 n 的向量的第 i 个元素(1≤i≤n+1)之前插入一个元素时,需向 后移动 n-i+1 个元素。 个

15. 向一个长度为 n 的向量中删除第 i 个元素(1≤i≤n)时,需向前移动 n-i 元素。 16. 在顺序表中访问任意一结点的时间复杂度均为 O(1) 随机存取 的数据结构。

,因此,顺序表也称为

17. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元 素的物理位置 不一定 相邻。

18.在单链表中,除了首元结点外,任一结点的存储位置由 其直接前驱结点的链 域的值 指示。

19. 在 n 个结点的单链表中要删除已知结点*p,需找到它的前驱结点的地址,其 时间复杂度为 O(n) 。 20. 向量、栈和队列都是 除元素; 对于栈只能在 入和 队首 线性 栈顶 结构,可以在向量的 任何 位置插入和删 队尾 插

插入和删除元素; 对于队列只能在

删除元素。 栈顶 。不允

21. 栈是一种特殊的线性表,允许插入和删除运算的一端称为 许插入和删除运算的一端称为 22. 队列 栈底 。

是被限定为只能在表的一端进行插入运算,在表的另一端进行删除

运算的线性表。 23. 不包含任何字符(长度为 0)的串 称为空白串。 称为目标串, 子串 称为空串; 由一个或多个空格(仅

由空格符)组成的串

24. 子串的定位运算称为串的模式匹配; 被匹配的主串 称为模式。

25. 假设有二维数组 A6×8,每个元素用相邻的 6 个字节存储,存储器按字节编址。 已知 A 的起始存储位置 (基地址) 1000, 为 则数组 A 的体积 (存储量) 为 末尾元素 A57 的第一个字节地址为 字节地址为 址为 (8+4)×6+1000=1072 1282 288 B ;

;若按行存储时,元素 A14 的第一个

;若按列存储时,元素 A47 的第一个字节地 。 5 种形态。 个分支结点和 26-1 =32

(6×7+4)×6+1000)=1276

26. 由3个结点所构成的二叉树有 27.

一棵深度为 6 的满二叉树有 n1+n2=0+ n2= n0-1=31

个叶子。 注:满二叉树没有度为 1 的结点,所以分支结点数就是二度结点数。

28. 一棵具有257个结点的完全二叉树,它的深度为 ( 注:用? log2(n) ?+1= ? 8.xx ?+1=9 29.设一棵完全二叉树有 700 个结点,则共有 答:最快方法:用叶子数=[n/2]=350 350

9



个叶子结点。

30. 设一棵完全二叉树具有 1000 个结点,则此完全二叉树有 500 有 499 个度为 2 的结点,有 1 个结点只有非空左子树,有

个叶子结点, 0 个结点

只有非空右子树。 答:最快方法:用叶子数=[n/2]=500 ,n2=n0-1=499。 另外,最后一结点为 2i 属于左叶子,右叶子是空的,所以有 1 个非空左子树。完全二叉树的特点决定不可 能有左空右不空的情况,所以非空右子树数=0. 31.在数据的存放无规律而言的线性表中进行检索的最佳方法是 查找) 。 顺序查找(线性

32. 线性有序表(a1,a2,a3,?,a256)是从小到大排列的,对一个给定的值 k,用 二分法检索表中与 k 相等的元素, 在查找不成功的情况下, 最多需要检索 设有 100 个结点,用二分法查找时,最大比较次数是 7 。 8 次。

33. 假设在有序线性表 a[20]上进行折半查找,则比较一次查找成功的结点数为 1; 比较两次查找成功的结点数为 查找长度为 3.7 。 2 ;比较四次查找成功的结点数为 8 ;*均

解:显然,*均查找长度=O(log2n)<5 次(25) 。但具体是多少次,则不应当按照 公式
ASL ? n ?1 n log
2

( n ? 1)

来计算(即(21×log221)/20=4.6 次并不正确!。因为这是在假设 )

n=2m-1 的情况下推导出来的公式。应当用穷举法罗列: 全 部 元 素 的 查 找 次 数 为 = ( 1 + 2 × 2 + 4 × 3 + 8 × 4 + 5 × 5 ) = 74 ; ASL =

74/20=3.7

!! !

34.折半查找有序表(4,6,12,20,28,38,50,70,88,100) ,若查找表中元 素 20,它将依次与表中元素 28,6,12,20 比较大小。 散列查

35. 在各种查找方法中,*均查找长度与结点个数 n 无关的查找方法是 找 。 关键字的值 决定数据的存储地址。

36. 散列法存储的基本思想是由

二、判断正误(在正确的说法后面打勾,反之打叉) ( × )1. 链表的每个结点中都恰好包含一个指针。 答:错误。链表中的结点可含多个指针域,分别存放多个指针。例如,双向链表中 的结点可以含有两个指针域,分别存放指向其直接前趋和直接后继结点的指针。 ( × )2. 链表的物理存储结构具有同链表一样的顺序。错,链表的存储结构特 点是无序,而链表的示意图有序。 ( × )3. 链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动 地将后续的各个单元向前移动。错,链表的结点不会移动,只是指针内容改变。 ( × )4. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一 个复杂类型。 错,混淆了逻辑结构与物理结构,链表也是线性表!且即使是顺序表,也能存放记 录型数据。 ( × )5. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。 错,正好说反了。顺序表才适合随机存取,链表恰恰适于“顺藤摸瓜” ( × )6. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。 错,前一半正确,但后一半说法错误,那是链式存储的优点。顺序存储方式插入、 删除运算效率较低,在表长为 n 的顺序表中,插入和删除一个数据元素,*均需移 动表长一半个数的数据元素。

( × )7. 线性表在物理存储空间中也一定是连续的。 错,线性表有两种存储方式,顺序存储和链式存储。后者不要求连续存放。 ( × )8. 线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序 上相邻。 错误。线性表有两种存储方式,在顺序存储时,逻辑上相邻的元素在存储的物理位 置次序上也相邻。 ( × )9. 顺序存储方式只能用于存储线性结构。 错误。顺序存储方式不仅能用于存储线性结构,还可以用来存放非线性结构,例如 完全二叉树是属于非线性结构,但其最佳存储方式是顺序存储方式。 (后一节介绍) ( × )10. 线性表的逻辑顺序与存储顺序总是一致的。 错,理由同 7。链式存储就无需一致。 ( × )11. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是

一个复杂类型。 错,线性表是逻辑结构概念,可以顺序存储或链式存储,与元素数据类型无关。 ( × )12. 在表结构中最常用的是线性表,栈和队列不太常用。

错,不一定吧?调用子程序或函数常用,CPU 中也用队列。 ( √ )13. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是

一种后进先出型结构。 ( √ )14. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可

以是线性表。 正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同 而已。 ( × )15. 栈和链表是两种不同的数据结构。

错,栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同

类项。 ( × )16. 栈和队列是一种非线性数据结构。

错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不 同而已。 ( √ ( √ )17. 栈和队列的存储方式既可是顺序方式,也可是链接方式。 )18. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机

会,应把两个栈的栈底分别设在这片内存空间的两端。 ( × )19. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先

进后出型结构。 错,后半句不对。 ( × )20. 一个栈的输入序列是 12345,则栈的输出序列不可能是 12345。

错,有可能。 ( √ )21. 若二叉树用二叉链表作存贮结构,则在 n 个结点的二叉树链表中只有 n—1 个非空指针域。 ( × )22.二叉树中每个结点的两棵子树的高度差等于 1。 ( √ )23.二叉树中每个结点的两棵子树是有序的。 ( × )24.二叉树中每个结点有两棵非空子树或有两棵空子树。 ( × )25.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结 点的关键字值,且小于其右非空子树(若存在的话)所有结点的关键字值。 当是二叉排序树的特点) ( × )26.二叉树中所有结点个数是 2k-1-1,其中 k 是树的深度。 (应 2i-1) ( × )27.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。 ( × )28.对于一棵非空二叉树,它的根结点作为第一层,则它的第 i 层上最多能 有 2i—1 个结点。 (应 2i-1) (应

( √ )29.用二叉链表法(link-rlink)存储包含 n 个结点的二叉树,结点的 2n 个指针区域中有 n+1 个为空指针。 ( √ )30.具有 12 个结点的完全二叉树有 5 个度为 2 的结点。 三、单项选择题 ( B )1. 非线性结构是数据元素之间存在一种: B)多对多关系 C)多对一关系 D)一对一关系 结构;

A)一对多关系 ( C

)2. 数据结构中,与所使用的计算机无关的是数据的 B) 物理 C) 逻辑

A) 存储 ( C

D) 物理和存储

)3. 算法分析的目的是: B) 研究算法中的输入和输出的关系 D) 分析算法的易懂性和文档性

A) 找出数据结构的合理性 C) 分析算法的效率以求改进 ( A

)4. 算法分析的两个主要方面是: B) 正确性和简明性 D) 数据复杂性和程序复杂性

A) 空间复杂性和时间复杂性 C) 可读性和文档性 ( C )5. 计算机算法指的是: B) 排序方法

A) 计算方法 法 ( B

C) 解决问题的有限运算序列

D) 调度方

)6. 计算机算法必须具备输入、输出和

等 5 个特性。

A) 可行性、可移植性和可扩充性 C) 确定性、有穷性和稳定性 ( C

B) 可行性、确定性和有穷性 D) 易读性、稳定性和安全性

)7.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续

的,称之为: (A)存储结构 储结构 (B)逻辑结构 (C)顺序存储结构 (D)链式存



B

)8.一个向量第一个元素的存储地址是 100,每个元素的长度为 2,则第 5

个元素的地址是 (A)110 ( A (B)108 (C)100 (D)120

)9. 在 n 个结点的顺序表中,算法的时间复杂度是 O(1)的操作是: 访问第 i 个结点(1≤i≤n)和求第 i 个结点的直接前驱(2≤i≤n) 在第 i 个结点后插入一个新结点(1≤i≤n) 删除第 i 个结点(1≤i≤n) 将 n 个结点从小到大排序 )10. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不 个元素 (C)63 (D)7

(A) (B) (C) (D) ( B

变,*均要移动 (A)8 ( A

(B)63.5

)11. 链接存储的存储结构所占存储空间:

(A) 分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针 (B) 只有一部分,存放结点值 (C) 只有一部分,存储表示结点间关系的指针 (D) 分两部分,一部分存放结点值,另一部分存放结点所占单元数 ( B )12. 链表是一种采用 (B)链式 存储结构存储的线性表; (C)星式 (D)网状

(A)顺序 ( D

)13. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址: (B)部分地址必须是连续的 (D)连续或不连续都可以 情况下适用于使用链式结构实现。 (B)需不断对L进行删除插入 (D)L中结点结构复杂

(A)必须是连续的 (C)一定是不连续的 ( B )14. 线性表L在

(A)需经常修改L中的结点值 (C)L中含有大量的结点



B

)15.栈中元素的进出原则是 B.后进先出 C.栈空则进 D.栈满则出

A.先进先出 ( C

)16. 若已知一个栈的入栈序列是 1,2,3,?,n,其输出序列为 p1,p2,

p3,?,pn,若 p1=n,则 pi 为 A.i ( B B.n=i C.n-i+1 D.不确定

)17. 判定一个栈 ST(最多元素为 m0)为空的条件是 B . ST->top=0 C . ST->top<>m0

A . ST->top<>0 D.ST->top=m0



C )18. 在一个图中,所有顶点的度数之和等于图的边数的 A.1/2 B. 1 C. 2

倍。 D. 4

( 倍。

B

)19. 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的

A.1/2 ( B

B.

1

C. 条边。 C.

2

D.

4

)20. 有 8 个结点的无向图最多有 A.14 B. 28

56

D.

112 ( C )21. 有 8 个结点的有向完全图有 A.14 112 ( B )22.在表长为n的链表中进行线性查找,它的*均查找长度为 B. ASL=(n+1)/2; D. ASL≈log2(n+1)-1 B. 28 条边。 C. 56 D.

A. ASL=n; C. ASL= ( A
n

+1;

)23.折半查找有序表(4,6,10,12,20,30,50,70,88,100) 。若

查找表中元素 58,则它将依次与表中 A.20,70,30,50 50 ( C B.30,88,70,50

比较大小,查找结果是失败。 C.20,50 D.30,88,

)24.对 22 个记录的有序表作折半查找,当查找失败时,至少需要比较

次关键字。 A.3 ( A B.4 )25. 链表适用于 B.二分法 C.5 查找 C.顺序,也能二分法 D.随机 D. 6

A.顺序

《数据结构与算法》复*题 一、选择题。 1.在数据结构中,从逻辑上可以把数据结构分为 A.动态结构和静态结构 C.线性结构和非线性结构 C 。

B.紧凑结构和非紧凑结构 D.内部结构和外部结构 A 。 D.数据元素之间的

2.数据结构在计算机内存中的表示是指 A.数据的存储结构 关系 B.数据结构

C.数据的逻辑结构

3.在数据结构中,与所使用的计算机无关的是数据的 A.逻辑 B.存储 C.逻辑和存储

A

结构。

D.物理 C 。

4.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 A.数据的处理方法 C.数据元素之间的关系 B.数据元素的类型 D.数据的存储方法 A 。

5.在决定选取何种存储结构时,一般不考虑

A.各结点的值如何 C.对数据有哪些运算 6.以下说法正确的是 D

B.结点个数的多少 D.所用的编程语言实现这种结构是否方便。 。

A.数据项是数据的基本单位 B.数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构

7.算法分析的目的是

C

,算法分析的两个主要方面是

A



(1)A.找出数据结构的合理性 C.分析算法的效率以求改进 (2)A.空间复杂度和时间复杂度 C.可读性和文档性

B.研究算法中的输入和输出的关系 C.分析算法的易读性和文档性 B.正确性和简明性 D.数据复杂性和程序复杂性

8.下面程序段的时间复杂度是 O(n2) s =0; for( I =0; i<n; i++) for(j=0;j<n;j++) s +=B[i][j]; sum = s ;



9.下面程序段的时间复杂度是 O(n*m) for( i =0; i<n; i++) for(j=0;j<m;j++)



A[i][j] = 0;

10.下面程序段的时间复杂度是 O(log3n) i = 0; while(i<=n) i = i * 3;



11.在以下的叙述中,正确的是

B



A.线性表的顺序存储结构优于链表存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出

12.通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 A.数据元素具有同一特点

B 。

B.不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致 C.每个数据元素都一样 D.数据元素所包含的数据项的个数要相等

13.链表不具备的特点是 A.可随机访问任一结点 C.不必事先估计存储空间

A

。 B.插入删除不需要移动元素 D.所需空间与其长度成正比

14.不带头结点的单链表 head 为空的判定条件是

A



A.head == NULL C.head->next ==head

B head->next ==NULL D head!=NULL

15.带头结点的单链表 head 为空的判定条件是 A.head == NULL C.head->next ==head

B



B head->next ==NULL D head!=NULL

16. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点, 则采用 D A.单链表 环链表 存储方式最节省运算时间。 B.给出表头指针的单循环链表 C.双链表 D.带头结点的双循

17.需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。 B.静态链表 C.线性链表 D.顺序存储结构

A.单链表

18.非空的循环单链表 head 的尾结点(由 p 所指向)满足 A.p->next == NULL C.p->next ==head B.p == NULL D.p == head

C



19.在循环双链表的 p 所指的结点之前插入 s 所指结点的操作是

D



A.p->prior = s;s->next = p;p->prior->next = s;s->prior = p->prior B.p->prior = s;p->prior->next = s;s->next = p;s->prior = p->prior

C.s->next = p;s->prior = p->prior;p->prior = s;p->prior->next = s D.s->next = p;s->prior = p->prior;p->prior->next = s;p->prior = s

20. 如果最常用的操作是取第 i 个结点及其前驱, 则采用 D A.单链表 B.双链表 C.单循环链表 D. 顺序表

存储方式最节省时间。

21.在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复 杂度是 B 。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n)

22.在一个长度为 n(n>1)的单链表上,设有头和尾两个指针,执行 链表的长度有关。 A.删除单链表中的第一个元素 B.删除单链表中的最后一个元素 C.在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素

B 操作与

23.与单链表相比,双链表的优点之一是 D A.插入、删除操作更简单 B.可以进行随机访问 C.可以省略表头指针或表尾指针 D.顺序访问相邻结点更灵活



24.如果对线性表的操作只有两种,即删除第一个元素,在最后一个元素的后面插

入新元素,则最好使用

B



A.只有表头指针没有表尾指针的循环单链表 B.只有表尾指针没有表头指针的循环单链表 C.非循环双链表 D.循环双链表

25.在长度为 n 的顺序表的第 i 个位置上插入一个元素(1≤ i ≤n+1) ,元素的移 动次数为: A.n – i + 1 A 。 B.n – i C.i D.i – 1

26. 对于只在表的首、 尾两端进行插入操作的线性表, 宜采用的存储结构为 A.顺序表 B. 用头指针表示的循环单链表 C.用尾指针表示的循环单链表 D.单链表

C



27.下述哪一条是顺序存储结构的优点? A 插入运算方便 C 存储密度大

C



B 可方便地用于各种逻辑结构的存储表示 D 删除运算方便

28.下面关于线性表的叙述中,错误的是哪一个?

B



A 线性表采用顺序存储,必须占用一片连续的存储单元 B 线性表采用顺序存储,便于进行插入和删除操作。 C 线性表采用链式存储,不必占用一片连续的存储单元 D 线性表采用链式存储,便于进行插入和删除操作。

29.线性表是具有 n 个

B

的有限序列。

A.字符

B.数据元素

C.数据项

D.表元素

30. n 个结点的线性表的数组实现中, 在 算法的时间复杂度是 O 1) ( 的操作是 A.访问第 i(1<=i<=n)个结点和求第 i 个结点的直接前驱(1<i<=n) B.在第 i(1<=i<=n)个结点后插入一个新结点 C.删除第 i(1<=i<=n)个结点 D.以上都不对

A



31.若长度为 n 的线性表采用顺序存储结构,在其第 i 个位置插入一个新元素的算 法的时间复杂度为 A.O(0) C 。 C.O(n) D.O(n2)

B.O(1)

32.对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为 A.O(n) O(n) B.O(n) O(1) C.O(1) O(n)

C



D.O(1) O(1)

33.线性表(a1,a2, 为 C A.O(0) 。

? ,an)以链式方式存储,访问第 i 位置元素的时间复杂度

B.O(1)

C.O(n)

D.O(n2)

34.单链表中,增加一个头结点的目的是为了 C A.使单链表至少有一个结点 C.方面运算的实现



B.标识表结点中首结点的位置 D.说明单链表是线性表的链式存储

35.在单链表指针为 p 的结点之后插入指针为 s 的结点,正确的操作是

B



A.p->next=s;s->next=p->next C.p->next=s;p->next=s->next

B. s->next=p->next ;p->next=s; D.p->next=s->next;p->next=s

36.线性表的顺序存储结构是一种 A A.随机存取的存储结构 C.索引存取的存储结构

。 B.顺序存取的存储结构 D.Hash 存取的存储结构

37.栈的特点是 A.先进先出

B

,队列的特点是 B.先进后出

A



38.栈和队列的共同点是 C A.都是先进后出

。 B.都是先进先出 D.没有共同点

C.只允许在端点处插入和删除元素

39.一个栈的进栈序列是 a,b,c,d,e,则栈的不可能的输出序列是 A.edcba B.decba C.dceab D.abcde

C



40.设有一个栈,元素依次进栈的顺序为 A、B、C、D、E。下列 出栈序列。 A.A,B,C,D,E B.B,C,D,E,A C.E,A,B,C,D

C

是不可能的

D.E,D,C,B,A

41.以下

B

不是队列的基本运算? B.从队列中删除第 i 个元素 D.读取队头元素的值

A.从队尾插入一个新元素 C.判断一个队列是否为空

42.若已知一个栈的进栈序列是 1,2,3, ,n,其输出序列为 p1,p2,p3,?,pn, 若 p1=n,则 pi 为 A.i B.n-i C 。 D.不确定

C.n-i+1

43.判定一个顺序栈 st(最多元素为 MaxSize)为空的条件是 B A.st->top != -1 C.st->top != MaxSize B.st->top == -1 D. st->top == MaxSize



44.判定一个顺序栈 st(最多元素为 MaxSize)为满的条件是 D A.st->top != -1 C.st->top != MaxSize B.st->top == -1 D.st->top == MaxSize



45.一个队列的入队序列是 1,2,3,4,则队列的输出序列是 B A.4,3,2,1 C.1,4,3,2 B.1,2,3,4 D.3,2,4,1



46.判定一个循环队列 qu(最多元素为 MaxSize)为空的条件是 C A . qu->rear – qu->front ==MaxSize -1==MaxSize C.qu->rear ==qu->front



B . qu->rear – qu->front

D. qu->rear =qu->front -1

47.在循环队列中,若 front 与 rear 分别表示对头元素和队尾元素的位置,则判 断循环队列空的条件是 C 。

A. front==rear+1

B. rear==front+1

C. front==rear

D. front==0

48. 向一个栈顶指针为 h 的带头结点的链栈中插入指针 s 所指的结点时, 应执行 操作。 A.h->next=s ; C.s->next=h ;h =s ; B.s->next=h ; D.s->next=h->next ;h->next=s ;

D

49.输入序列为 ABC,可以变为 CBA 时,经过的栈操作为 A.push,pop,push,pop,push,pop C.push,push,pop, pop,push,pop

B



B.push,push,push,pop, pop, pop D.push,pop,push,push,pop, pop

50.若栈采用顺序存储方式存储,现两栈共享空间 V[1

m],top[1]、top[2]分别

代表第 1 和第 2 个栈的栈顶,栈 1 的底在 V[1],栈 2 的底在 V[m],则栈满的条件是 B 。 A . |top[2]-top[1]|=0 D.top[1]=top[2] B . top[1]+1=top[2] C . top[1]+top[2]=m

51.设计一个判别表达式中左、右括号是否配对出现的算法,采用 最佳。 A.线性表的顺序存储结构 B.队列

D

数据结构

C.线性表的链式存储结构

D.栈

52.允许对队列进行的操作有 D A.对队列中的元素排序 C.在队头元素之前插入元素

。 B.取出最*进队的元素 D.删除队头元素

53.对于循环队列

D

。 B.无法判断队列是否为满 D.以上说法都不对

A.无法判断队列是否为空 C.队列不可能满

54.若用一个大小为 6 的数值来实现循环队列,且当前 rear 和 front 的值分别为 0 和 3,当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为 B 。 A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 1

55.队列的“先进先出”特性是指

D



A.最早插入队列中的元素总是最后被删除 B.当同时进行插入、删除操作时,总是插入操作优先 C.每当有删除操作时,总是要先做一次插入操作 D.每次从队列中删除的总是最早插入的元素

56.和顺序栈相比,链栈有一个比较明显的优势是 A A.通常不会出现栈满的情况 C.插入操作更容易实现



B. 通常不会出现栈空的情况 D.删除操作更容易实现

57.用不带头结点的单链表存储队列,其头指针指向队头结点,尾指针指向队尾结 点,则在进行出队操作时 A.仅修改队头指针 C.队头、队尾指针都可能要修改 C 。 B.仅修改队尾指针 D.队头、队尾指针都要修改

58.若串 S=‘software’ ,其子串的数目是 A.8 B.37 C.36 D.9

B



59.串的长度是指

B

。 B.串中所含字符的个数 D.串中所含非空格字符的个数

A.串中所含不同字母的个数 C.串中所含不同字符的个数

60.串是一种特殊的线性表,其特殊性体现在 B A.可以顺序存储 C.可以链式存储 B.数据元素是一个字符



D.数据元素可以是多个字符

61.设有两个串 p 和 q,求 q 在 p 中首次出现的位置的运算称为 B A.连接 B. 模式匹配 C.求子串 D.求串长



62.数组 A 中,每个元素的长度为 3 个字节,行下标 i 从 1 到 8,列下标 j 从 1 到 10,从首地址 SA 开始连续存放的存储器内,该数组按行存放,元素 A[8][5]的起始 地址为 C 。 C.SA+222 D.SA+225

A.SA+141 B. SA+144

63.数组 A 中,每个元素的长度为 3 个字节,行下标 i 从 1 到 8,列下标 j 从 1 到 10,从首地址 SA 开始连续存放的存储器内,该数组按行存放,元素 A[5][8]的起始 地址为 C 。 C.SA+222 D.SA+225

A.SA+141 B. SA+180

64.若声明一个浮点数数组如下: froat average[]=new float[30]; 假设该数组的内存起始位置为 200, average[15]的内存地址是 C A.214 B.215 C.260 D.256 。

65. 设二维数组 A[1? m,1? n]按行存储在数组 B 中, 则二维数组元素 A[i,j]在一 维数组 B 中的下标为 A 。 C.i*(j-1) D.j*m+i-1

A.n*(i-1)+j B. n*(i-1)+j-1

66.有一个 100×90 的稀疏矩阵,非 0 元素有 10,设每个整型数占 2 个字节,则用 三元组表示该矩阵时,所需的字节数是 A.20 B. 66 C.18 000 B 。

D.33

67.数组 A[0 ? 4,-1 ? -3,5 A.55 B. 45 C.36

?7]中含有的元素个数是 A D.16



68.对矩阵进行压缩存储是为了 A.方便运算 B. 方便存储

D

。 D.减少存储空间

C.提高运算速度

69.设有一个 10 阶的对称矩阵 A,采用压缩存储方式,以行序为主存储,a1,1 为第 一个元素,其存储地址为 1,每个元素占 1 个地址空间,则 a8,5 的地址为 B 。 A.13 B. 33 C.18 D.40

70.稀疏矩阵一般的压缩存储方式有两种,即 C



A.二维数组和三维数组 C.三元组和十字链表

B. 三元组和散列 D. 散列和十字链表

71.树最适合用来表示 A.有序数据元素

C 。 B.无序数据元素 D.元素之间无联系的数据

C.元素之间具有分支层次关系的数据

72.深度为 5 的二叉树至多有 A.16 B. 32 C. 31

C

个结点。 C. 10

73.对一个满二叉树,m 个叶子,n 个结点,深度为 h,则 D A.n = h+m B h+m = 2n C m = h-1 D n = 2h-1



74. 任何一棵二叉树的叶子结点在前序、 中序和后序遍历序列中的相对次序 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对

A



75.在线索化树中,每个结点必须设置一个标志来说明它的左、右链指向的是树结 构信息,还是线索化信息,若 0 标识树结构信息,1 标识线索,对应叶结点的左 右链域,应标识为__ D __。 A.00 B.01 C.10 D.11

76.在下述论述中,正确的是

D



①只有一个结点的二叉树的度为 0; ②二叉树的度为 2; ③二叉树的左右子树可任意 交换;

④深度为 K 的顺序二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④ D.①④

77.设森林 F 对应的二叉树为 B,它有 m 个结点,B 的根为 p,p 的右子树的结点个 数为 n,森林 F 中第一棵树的结点的个数是 A.m-n B.m-n-1 C.n+1 A 。

D.不能确定

78.若一棵二叉树具有 10 个度为 2 的结点,5 个度为 1 的结点,则度为 0 的结点的 个数是 B 。 A.9 B.11 C.15 D.不能确定

79.具有 10 个叶子结点的二叉树中有 A.8 B.9 C.10 D.11

B

个度为 2 的结点。

80.在一个无向图中,所有顶点的度数之和等于所有边数的 A.1/2 B 1 C 2 D 4

C

倍。

81.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的 A.1/2 B 1 C 2 D 4

B 倍。

82.某二叉树结点的中序序列为 ABCDEFG,后序序列为 BDCAFGE,则其左子树中结点 数目为: C A.3 B.2 C.4 D.5

83.已知一算术表达式的中缀形式为 A+B *C–D/E,后缀形式为 ABC *+DE/–,其

前缀形式为 A . –A+B*C/DE +A*BC/DE

D

。 B. – A+B*CD/E C – +*ABC/DE D. –

84.已知一个图,如图所示,若从顶点 a 出 法进行遍历,则可能得到的一种顶点序列为 广度搜索法进行遍历,则可能得到的一种顶 ___A___; ①A.a,b,e,c,d,f C.a,e,b,c,f,d, ②A.a,b,c,e,d,f C.a,e,b,c,f,d,
b

a

发按深度搜索
e c

____D___ ; 按 点 序 列 为

d

f

B.a,c,f,e,b,d D.a,e,d,f,c,b B.a,b,c,e,f,d D.a,c,f,d,e,b

85.采用邻接表存储的图的深度优先遍历算法类似于二叉树的___A____。 A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历

86.采用邻接表存储的图的广度优先遍历算法类似于二叉树的___D____。 A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历

87.具有 n 个结点的连通图至少有 A. n-1 B. n

A

条边。 D. 2n

C. n(n-1)/2

88.广义表( ,a)的表头是 C (a) A.a B () C (a)

,表尾是 C 。 D ( ) (a)

89.广义表( )的表头是 C (a) A.a B () C (a)

,表尾是 B D ( ) (a)



90.顺序查找法适合于存储结构为 A 散列存储

B

的线性表。 C 压缩存储 D 索引存储

B 顺序存储或链式存储

91.对线性表进行折半查找时,要求线性表必须 B A C 以顺序方式存储 以链式方式存储



B 以顺序方式存储,且结点按关键字有序排列 D 以链式方式存储,且结点按关键字有序排列

92.采用折半查找法查找长度为 n 的线性表时,每个元素的*均查找长度为 D 。 B O(nlog2n) C O(n) D O(log2n)

A O(n2)

93.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100} ,当 折半查找值为 82 的结点时, C A. 11 B 5 次比较后查找成功。 C 4 D 8

94.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法 A 正确 B 错误 B 。

95.下面关于 B 树和 B+树的叙述中,不正确的结论是

A



A B 树和 B+树都能有效的支持顺序查找 查找 C B 树和 B+树都是*衡的多叉树 构

B B 树和 B+树都能有效的支持随机

D B 树和 B+树都可用于文件索引结

96.以下说法错误的是

B



A.散列法存储的思想是由关键字值决定数据的存储地址 B.散列表的结点中只包含数据元素自身的信息,不包含指针。 C.负载因子是散列表的一个重要参数,它反映了散列表的饱满程度。 D.散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。

97.查找效率最高的二叉排序树是 C



A.所有结点的左子树都为空的二叉排序树。 B.所有结点的右子树都为空的二叉排序树。 C.*衡二叉树。 D.没有左子树的二叉排序树。

98.排序方法中,从未排序序列中依次取出元素与已排序序列中的元素进行比较, 将其放入已排序序列的正确位置上的方法,称为 A.希尔排序 B。冒泡排序 C 插入排序 C 。 D。选择排序

99.在所有的排序方法中,关键字比较的次数与记录的初始排列次序无关的是 D 。

A.希尔排序

B.冒泡排序

C.直接插入排序

D.直接选择排序

100.堆是一种有用的数据结构。下列关键码序列 A.94,31,53,23,16,72 C.16,53,23,94,31,72

D

是一个堆。

B.94,53,31,72,16,23 D.16,31,23,94,53,72

101.堆排序是一种 A.插入

B

排序。 C.交换 D.归并

B.选择

102.

D

在链表中进行操作比在顺序表中进行操作效率高。 B.折半查找 C.分块查找 D.插入

A.顺序查找

103.直接选择排序的时间复杂度为 A.O(n) B.O(log2n)

D

。 为元素个数) (n D. O(n2)

C.O(nlog2n)

二、填空题。 1.数据逻辑结构包括 线性结构 、 树形结构 。 、线性结构 、 树形结构 和 图状结构 和 图状结构 三种类型,树

形结构和图状结构合称 非线性结构 2.数据的逻辑结构分为 4 种。 集合

3.在线性结构中,第一个结点 没有 前驱结点,其余每个结点有且只有 1 结点;最后一个结点 没有

个前驱

后续结点,其余每个结点有且只有 1 个后续结点。

4. 线性结构中元素之间存在 一对一 关系, 树形结构中元素之间存在 一对多 关系, 图形结构中元素之间存在 多对多 关系。

5.在树形结构中,树根结点没有 前驱 结点,其余每个结点有且只有 1 个前驱结 点;叶子结点没有 后续 结点,其余每个结点的后续结点可以 任意多个 索引 和 散列 。 存储 。

6.数据结构的基本存储方法是 顺序 、 链式 、

7.衡量一个算法的优劣主要考虑正确性、可读性、健壮性和 时间复杂度与 空间 复杂度 。 8.评估一个算法的优劣,通常从 时间复杂度 察。 9.算法的 5 个重要特性是 有穷性 、 和 空间复杂度 可行性 两个方面考

确定性 、

、输入和输出。

10.在一个长度为 n 的顺序表中删除第 i 个元素时,需向前移动 n-i-1 个元素。 11.在单链表中,要删除某一指定的结点,必须找到该结点的 前驱 结点。

12.在双链表中,每个结点有两个指针域,一个指向 前驱 结点,另一个指向 后 继结点 。 13.在顺序表中插入或删除一个数据元素,需要*均移动 n 据元素的个数与 位置 有关。 14.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的 速度存取线性表的元素是,应采用 顺序 存储结构。 个数据元素,移动数

15.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成 单链表 和 双链表 。 表示元素之间的关系的; 链式存储结构是通过 指

16. 顺序存储结构是通过 下标 针 表示元素之间的关系的。

17.带头结点的循环链表 L 中只有一个元素结点的条件是 18.

L->next->next=L



栈 是限定仅在表尾进行插入或删除操作的线性表,其运算遵循 后进先出

的原则。 19.空串是 零个字符的串 ,其长度等于 零。空白串是由一个或多个空格字符组

成的串,其长度等于其包含的空格个数。 20.组成串的数据元素只能是 单个字符 。

21.一个字符串中 任意个连续字符构成的部分 称为该串的子串。 22.子串 ”str” 在主串 ”datastructure” 中的位置是 5 。

23.二维数组 M 的每个元素是 6 个字符组成的串,行下标 i 的范围从 0 到 8,列下 标 j 的范围从 1 到 10, 则存放 M 至少需要 540 个字节; 的第 8 列和第 5 行共占 108 M 个字节。 24.稀疏矩阵一般的压缩存储方法有两种,即 三元组表 和 十字链表 。 25.广义表( ,(b) ,( ))的长度是 3 ,深度是 4 。 (a)( ,c)((d)) 26.在一棵二叉树中,度为零的结点的个数为 n0,度为 2 的结点的个数为 n2,则 有 n0= n2+1 。

27.在有 n 个结点的二叉链表中,空链域的个数为__n+1__。 28.一棵有 n 个叶子结点的哈夫曼树共有__2n-1_个结点。 29.深度为 5 的二叉树至多有 31 个结点。

30.若某二叉树有 20 个叶子结点,有 30 个结点仅有一个孩子,则该二叉树的总结 点个数为 69 。

31.某二叉树的前序遍历序列是 abdgcefh,中序序列是 dgbaechf,其后序序列为 gdbehfca 。 32.线索二叉树的左线索指向其 遍历序列中的前驱 列中的后继 。 ,右线索指向其遍历序

33.在各种查找方法中,*均查找长度与结点个数 n 无关的查找方法是 散列查找 法 。 索引表 , 然后查找相应的 块表 。

34. 在分块索引查找方法中, 首先查找

35. 一个无序序列可以通过构造一棵 二叉排序 树而变成一个有序序列, 构造树的 过程即为对无序序列进行排序的过程。 36.具有 10 个顶点的无向图,边的总数最多为__45__。 37.已知图 G 的邻接表如图所示,其从顶点 v1 出发的深度优先搜索序列为 _v1v2v3v6v5v4_,其从顶点 v1 出发的广度优先搜索序列为_v1v2v5v4v3v6__。
v1 v2 v3 v4 v5 v6
∧ ∧

v2 v3 v6


v5 v5


v4



v4

v6

v3



38.索引是为了加快检索速度而引进的一种数据结构。一个索引隶属于某个数据记 录集, 它由若干索引项组成, 索引项的结构为 关键字 和 关键字对应记录的地址 。

39.Prim 算法生成一个最小生成树每一步选择都要满足 边的总数不超过 n-1 , 当前选择的边的权值是候选边中最小的 ,选中的边加入树中不产生回路 三项原 则。 40. 在一棵 m 阶 B 树中, 除根结点外, 每个结点最多有 m 棵子树, 最少有 m/2 子树。 三、判断题。 1.在决定选取何种存储结构时,一般不考虑各结点的值如何。 (√) 2.抽象数据类型(ADT)包括定义和实现两方面,其中定义是独立于实现的,定义 仅给出一个 ADT 的逻辑特性,不必考虑如何在计算机中实现。(√ ) 3.抽象数据类型与计算机内部表示和实现无关。 (√ ) ) 棵

4.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。 × (

5. 线性表采用链式存储结构时, 结点和结点内部的存储空间可以是不连续的。 × ) (

6.对任何数据结构链式存储结构一定优于顺序存储结构。 × ) ( 7.顺序存储方式只能用于存储线性结构。 × ) ( 8.集合与线性表的区别在于是否按关键字排序。 × ) ( 9.线性表中每个元素都有一个直接前驱和一个直接后继。 × ) ( 10.线性表就是顺序存储的表。 × ( ) )

11.取线性表的第 i 个元素的时间同 i 的大小有关。 × ( 12.循环链表不是线性表。 × ) (

13.链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺 序表中效率高。 √ ( )

14.双向链表可随机访问任一结点。 (× ) 15.在单链表中,给定任一结点的地址 p,则可用下述语句将新结点 s 插入结点 p 的后面 :p->next = s; s->next = p->next; (× ) 16.队列是一种插入和删除操作分别在表的两端进行的线性表,是一种先进后出的 结构。 × ( )

17. 串是一种特殊的线性表,其特殊性体现在可以顺序存储。 × ) ( 18.长度为 1 的串等价于一个字符型常量。(× ) 19.空串和空白串是相同的。 (×) 20.数组元素的下标值越大,存取时间越长。(× ) 21.用邻接矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间 大小只与图中结点个数有关,而与图的边数无关。(√ ) 22.一个广义表的表头总是一个广义表。 (× )

23.一个广义表的表尾总是一个广义表。 √ ) ( 24.广义表((( a ), b), c ) 的表头是(( a ), b),表尾是( c )。 √ ) ( 25.二叉树的后序遍历序列中,任意一个结点均处在其孩子结点的后面。 √ ) ( 26.度为 2 的有序树是二叉树。 × ) ( 27.二叉树的前序遍历序列中,任意一个结点均处在其孩子结点的前面。 √ ) ( 28.用一维数组存储二叉树时,总是以前序遍历顺序存储结点。 (×)

29.若已知一棵二叉树的前序遍历序列和后序遍历序列,则可以恢复该二叉树。 ( × ) 30.在哈夫曼树中,权值最小的结点离根结点最*。(× ) 31.强连通图的各顶点间均可达。 √ ( )

32.对于任意一个图,从它的某个结点进行一次深度或广度优先遍历可以访问到该 图的每个顶点。 × ( )

33.在待排序的记录集中,存在多个具有相同键值的记录,若经过排序,这些记录 的相对次序仍然保持不变,称这种排序为稳定排序。(√ ) 34.在*衡二叉树中,任意结点左右子树的高度差(绝对值)不超过 1。(√ ) 35.*伺判蚴前 AOE 网中每个结点事件的最早发生时间对结点进行排序。(× ) 36.冒泡排序算法关键字比较的次数与记录的初始排列次序无关。 × ) ( 37.对线性表进行折半查找时,要求线性表必须以链式方式存储,且结点按关键字 有序排列。 (× ) 38.散列法存储的思想是由关键字值决定数据的存储地址。 (√ )

39.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。 (× )

40. 具有 n 个结点的二叉排序树有多种, 其中树高最小的二叉排序树是最佳的。 √) (




友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版