上方(或下方)的所有元素均为零时,称该矩阵为______________。
39、对于上三角形和下三角形矩阵,分别以按行存储和按列存储原则进行压缩存储到数组M[k]中,若矩阵中非0元素为Aij,则k对应为________和__________。
40、设有一上三角形矩阵A[5][5]按行压缩存储到数组B中,B[0]的地址为100,每个元素占2个单元,则A[3][2]地址为____________。
41、广义表(A,(a,b),d,e,((i,j),k)),则广义表的长度为___________,深度为___________。 42、已知广义表A=((a,b,c),(d,e,f)),则运算head(head (tail(A))))=___ ________。
43、已知广义表ls =(a,(b,c,d),e),运用head和tail函数取出ls中的原子b的运算是_____。
44、在树结构里,有且仅有一个结点没有前驱,称为根。非根结点有且仅有一个___________,且存在一条从根到该结点的_______________。
45、度数为0的结点,即没有子树的结点叫作__________结点或_________结点。同一个结点的儿子结点之间互称为___________结点。
46、假定一棵树的广义表为A(B(e),C(F(h,i,j),g),D),则该树的度为___________,树的深度为_________,终端结点为______,单分支结点为,双分支结点个数为 _______,三分支结点为_______,C结点的双亲结点是______,孩子结点是______。
48、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中,与数据的存储结构有关系的是_____________。
47、有三个结点的二叉树,最多有________种形状。
48、每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换位置,这种排序方法成为_____________排序法。
49、高度为k的二叉树具有的结点数目,最少为_____,最多为_____。
50、对任何一棵二叉树,若n0,n1,n2分别是度为0,1,2的结点的个数,则n0=_______。 51、在含100个结点的完全二叉树,叶子结点的个数为_______。
52、将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列叫_____。 53、若一棵满二叉树含有121个结点,则该树的深度为_________。 54、一个具有767个结点的完全二叉树,其叶子结点个数为________。 55、深度为90的满二叉树,第11层有________个结点。 56、有100个结点的完全二叉树,深度为________。
57、设一棵二叉树中度为2的结点10个,则该树的叶子个数为________。
58、若待散列的序列为(18,25,63,50,42,32,9),散列函数为H(key)=key MOD 9,与18发生冲突的元素有_____________个。
59、含有3个2度结点和4个叶结点的二叉树可含__________个1度结点。 60、一棵具有5层满二叉树中节点总数为___________。
61、一棵含有16个结点的完全二叉树,对他按层编号,对于编号为7的结点,他的双亲结点及左右结点编号为______、______、_______。
62、深度为k(设根的层数为1)的完全二叉树至少有_______个结点, 至多有_______个结点。 63、若要对某二叉排序树进行遍历,保证输出所有结点的值序列按增序排列,应对该二叉排序树采用________遍历法。
64、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24,需要进行______________次元素之间的比较。
65、设有10个值,构成哈夫曼树,则该哈夫曼树共有______个结点。
66、从树中一个结点到另一个结点之间的分支构成这两个结点之间的____________。
67、关键字自身作为哈希函数,即H(k)=k,也可自身加上一个常数作为哈希函数,即H(k)=k+C这种构造哈希函数的方式叫____________。
68、对于一个图G,若边集合E(G)为无向边的集合,则称该图为____________。 69、对于一个图G,若边集合E(G)为有向边的集合,则称该图为____________。
70、对于有向图,顶点的度分为入度和出度,以该顶点为终点的边数目叫________;以该顶点为起点的边数目叫_________。
71、一个无向图采用邻接矩阵存储方法,其邻接矩阵一定是一个______________。 72、有一个n个顶点的有向完全图的弧数_____________。
73、在无向图中,若从顶点A到顶点B存在_________,则称A与B之间是连通的。 74、在一个无向图中,所有顶点的度数之和等于所有边数的___________倍。
75、一个连通图的生成树是该图的____________连通子图。若这个连通图有n个顶点, 则它的生成树有__________条边。
76、无向图的邻接矩阵是一个_____________矩阵。
77、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是_____ _______。
78、若采用邻接表的存储结构,则图的广度优先搜索类似于二叉树的____________遍历。 79、若图的邻接矩阵是对称矩阵,则该图一定是________________。
80、从如图所示的临接矩阵可以看出,该图共有______个顶点。如果是有向图,该图共有______条弧;如果是无向图,则共有________条边。 81、如果从一个顶点出发又回到该顶点,则此路径叫做___________。
82、一个具有个n顶点的无向图中,要连通全部顶点至少需要________条边。 B?83、给定序列{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它一定_________堆。
84、从未排序序列中选择一个元素,该元素将当前参加排序的那些元素分成前后两个部分,前一部分中所有元素都小于等于所选元素,后一部分中所有元素都大于或等于所选元素,而此时所选元素处在排序的最终位置。这种排序法称为_____________排序法。
85、折半搜索只适合用于___________________。
86、结点关键字转换为该结点存储单元地址的函数H称为_____________或叫__________。 87、在索引查找中,首先查找________,然后查找相应的_________,整个索引查找的平均查找长度
A B C ?011?A?001?B????010??C等于查找索引表的平均长度与查找相应子表的平均查找长度的_______。
三、选择题:
( )1.数据结构通常是研究数据的 及它们之间的联系。
A存储和逻辑结构 C理想和抽象
B存储和抽象 D理想与逻辑
( )2.在堆栈中存取数据的原则是 。
A先进先出 C先进后出
B后进先出
D随意进出
( )3.将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子的编号为______。
( )4.对于如图所示二叉树采用中根遍历,正确的遍历序列应为( )
( )5.设有100个元素,用折半查找法进行查找时,最大比较次数是_____ 。
( )6.快速排序在_____情况下最易发挥其长处。
A.被排序数据中含有多个相同排序码 B.被排序数据已基本有序
C.被排序数据完全无序 D.被排序数据中最大值和最小值相差悬殊 ( )7.由两个栈共享一个向量空间的好处是______。
A减少存取时间,降低下溢发生的机率 B节省存储空间,降低上溢发生的机率 C减少存取时间,降低上溢发生的机率 D节省存储空间,降低下溢发生的机率 ( )8.某二叉树的前序和后序序列正好相反,则该二叉树一定是_____的二叉树
A空或者只有一个结点 C任一结点无左孩子
B高度等于其结点数 D任一结点无右孩子
( )9.设散列表长m=14,散列函数H(K)=K%11,已知表中已有4个结点:r(15)=4; r(38)=5; r(61)=6;r(84)=7,其他地址为空,如用二次探测再散列处理冲突,关键字为49的结点地址是________。
A8
B3 D9
C5
( )10.在含有n个项点有e条边的无向图的邻接矩阵中,零元素的个数为________。
( )11.图的深度优先遍历类似于二叉树的_______。
A.先序遍历 C.后序遍历
B.中序遍历 D.层次遍历
( )12.设长度为n的链队列用单循环链表表示,若只设头指针,则入队操作的时间复杂度为_______。
A. O(1)
B. O(log2n) D. O(n2)
C. O(n)
( )13.堆的形状是一棵_______。
A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树
( )14.一个无向连连通图的生成树是含有该连通图的全部项点的_______。
A.极小连通子图 B.极小子图 C.极大连通子图 D.极大子图
( )15.一个序列中有10000个元素,若只想得到其中前10个最小元素,最好采用_______方法
A.快速排序
B.堆排序
C.插入排序 D.二路归并排序 ( )16.设单链表中结点的结构为
typedef struct node { ElemType data; struct node * Link; } 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
{ data; node * Link; ListNode;
非空的循环单链表first的尾结点(由p所指向)满足:______
A. p->link == NULL; B. p == NULL; C. p->link == first; D. p == first;
( )18.计算机识别、存储和加工处理的对象被统称为_________
A.数据
B.数据元素 D.数据类型
C.数据结构
( )19.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是
________
A.O(1) (nlogn)
(n)
(n2)
( )20.队和栈的主要区别是________
A.逻辑结构不同 B.存储结构不同
C.所包含的运算个数不同 D.限定插入和删除的位置不同 ( )21.链栈与顺序栈相比,比较明显的优点是________
A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况
( )22.在目标串T[0…n-1]=”xwxxyxy”中,对模式串p[0…m-1]=”xy”进行子串定位操作的结果
_______
( )23.已知广义表的表头为A,表尾为(B,C),则此广义表为________
A.(A,(B,C)) C.(A,B,C)
B.(A,B,C)
D.(( A,B,C))
( )24.二维数组A按行顺序存储,其中每个元素占1个存储单元。若A[1][1]的存储地址为420,
A[3][3]的存储地址为446,则A[5][5]的存储地址为_______
( )25.二叉树中第5层上的结点个数最多为________
( )26.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵,则此图是_______
A.有向完全图 C.强连通图
B.连通图 D.有向无环图
( )27.对n个关键字的序列进行快速排序,平均情况下的空间复杂度为_______
(1) (n)
(logn) (nlogn)
( )28.对于哈希函数H(key)=key,被称为同义词的关键字是_______
A.35和41 和44
和39
和51
( )29. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为________。