试卷详情
-
数据结构-10
-
[单项选择]从一个长度为n的顺序表中删除第i个元素(1≤i≤n)8寸,需要向前移动()。
A. n-i
B. n-i+1
C. n-i-1
D. i
-
[单项选择]在一个链队中,假设f和r分别为队首和队尾指针,则删除一个结点的运算是( )
A. r=f—>next
B. r=r—>next
C. f=f—>next
D. f=r—>next
-
[单项选择]对于一个具有N个结点和E条边的无向图,若采用邻接表示,则表头向量的大小是( )
A. N
B. N+1
C. N-E
D. N-1
-
[填空题]在______遍历二叉树的序列中,任何结点的子树上的所有结点,都是直接跟在该结点之后。
-
[单项选择]在一个具有n个单元的顺序栈中,假设栈底是存储地址的高端,现在我们以top作为栈顶指针,则作退栈操作时,top的变化是( )
A. top=top-1
B. top=top+1
C. top不变
D. top不确定
-
[填空题]拓扑排序指的是找一个有向图的______的过程。
-
[填空题]由权值为1,2,3,4,5,6的六个叶子结点构成一棵哈夫曼树,则带权的路径的长度为______。
-
[单项选择]在有向图中,所有顶点的入度之和是所有顶点出度之和的( )倍。
A. 0.5
B. 1
C. 2
D. 4
-
[单项选择]对采用二分查找法进行查找运算的查找表,要求按( )方式进行存储。
A. 顺序存储
B. 链式存储
C. 顺序存储且结点按关键字有序
D. 链式存储且结点按关键字有序
-
[填空题]存储在直接存储器上的顺序文件可以用顺序查找法存取,也可以用______和进行查找。
-
[填空题]在双向链表中,每个结点含有两个指针域,一个指向其______结点,另一个指向______结点。
-
[填空题]以下运算实现在链队上的出队列,请在______处用适当的语句予以填充。
int OutQueue(QueptrTp*lq,DataType*x)
{ LqueueTp*s;
if(1q—>front==lq—>rear){error("队空");return(0);}
else{ s=(lq—>front)—>next;
______=s—>data;
(lq—>front)—>next______;
if(s—>next==NULL)lq—>rear=lq—>front;
free(s);
return(1);
}
}
-
[简答题]假设有一个长度为n的有序序列,在进行查找时,可以借助二叉树来进行,请结合二叉树的性质来分析二分查找的最坏性能和平均性能。
-
[填空题]稀疏矩阵一般的压缩存储方法有2种,它们分别是______和______。
-
[填空题]在串的链式存储结构中,有一个串S1="ejidc",我们假设存储时结点的大小为1,并设指针占有4个字节,则链串的存储密度为______,又假设串S2="abcdefg"在存储时我们设定结点的大小为4,指针占有4个字节,则此链串的存储密度为______。
-
[单项选择]C语言数组Data[m+1]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作的语句为( )
A. front=front+1
B. front=(front+1)%m
C. rear=(rear+1)%m
D. front=(front+1)%(m+1)
-
[单项选择]如果以链表作为栈的存储结构,则退栈操作时( )
A. 必须判别栈是否满
B. 判别栈元素的类型
C. 必须判别栈是否空
D. 对栈不作任何判别
-
[填空题]以下算法实现若开散列表HP中无键值为K的结点,则插入一个这样的结点。请分析程序,并在______上填充合适的语句。
void insert_openhash(keytype K,openhash HP)
{ if(research_openhash(K,HP)==NULL)
{ i=H(K);
q=malloc(size);q—>key=______; /*生成新结点*/
______=HP[i];HP[i]=______; /*前插法链入新结点*/
}
}
-
[填空题]以下将ah,…am,和am+1…an,两个有序序列(它们相应的关键字值满足Kh≤Km,Km+1≤…Kn,)合并成一个有序序列Rh,…,Rn,(使其关键字值满足Kh,’≤…≤Kn,’)。请分析算法,并在______上填充适当的语句。
void merge(list a,list R,int h,int m,int n)
{i=h;k=h;j=m+1;
while((i<m)&&(j<=n))
{ if(a[i].key<=a[i].key){R[k]=______;______;}
else{R[k]=______;______;}
k++;
}
while(i<=______){R[k]=a[i];i++;k++;)
while(j<=______){R[k]=a[j];j++;k++;}
}
此算法的执行时间为______。
-
[单项选择]在桶排序中,其平均时间复杂度是( )
A. O(1)
B. O(
C. O(n2)
D. O(1g
-
[单项选择]一个队列的输入序列是1,2,3,4,则队列的输出序列是( )
A. 4,3,2,1
B. 1,2,3,4
C. 1,4,3,2
D. 3,2,4,1
-
[单项选择]倒排文件的主要优点是( )
A. 便于进行插入和删除运算
B. 便于进行文件的合并
C. 能大大提高基于非关键码数据项的查找速度
D. 能大大节省存储空间
-
[填空题]栈和队列均可视为特殊的线性表,所不同的在于对这二种特殊线性表______和______运算的限定不一样。
-
[填空题]以下运算实现在链栈上的进栈,请在______处用适当的语句予以填充。
void Push(LStackTp*ls,DataType x)
{ LStackTp*p;p=malloc(sizeof(LStackTp));
______;
p—>next=ls;
______;
}
-
[单项选择]森林T中有4棵树,第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后,其根结点的左孩子上有(
)个结点。
A. n1-1
B. n1
C. n1+n2+n3
D. n2+n3+n4
-
[单项选择]某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是bgbaechf,则其后序遍历的结点访问顺序是( )
A. bdgcefha
B. gdbecfha
C. bdgechfa
D. gdbehfca
-
[单项选择]在一棵完全二叉树的顺序存储方式中,若编号为t的结点有右孩子,则此结点右孩子的编号为( )
A. 2t
B. 2t-1
C. 2t+1
D. t/2
-
[单项选择]任何一个带权的无向连通图的最小生成树( )
A. 只有一棵
B. 有一棵或多棵
C. 一定有多棵
D. 可能不存在
-
[简答题]采用单链表作为存储结构,试编写一个函数来实现用选择排序方法进行升序排列。
-
[填空题]给定一个具有n个元素的向量,建立一个有序单链表的时间复杂度是()。