试卷详情
-
全国2010年10月自学考试数据结构试题
-
[简答题]
已知广义表如下: A=(B,y) B=(x,L) L=(a,b) 要求:
请画出广义表A对应的图形表示。
-
[简答题]
已知广义表如下: A=(B,y) B=(x,L) L=(a,b) 要求:
写出下列操作的结果tail(A)=_______________.head(B)=______________。
-
[单项选择]在图G中求两个结点之间的最短路径可以采用的算法是( )
A. 迪杰斯特拉(Dijkstra)算法
B. 克鲁斯卡尔(Kruskal)算法
C. 普里姆(Prim)算法
D. 广度优先遍历(BFS)算法
-
[单项选择]设有一个10阶的对称矩阵A,采用行优先压缩存储方式,a11为第一个元素,其存储地址为1,每个元素占一个字节空间,则a85的地址为( )
A. 13
B. 18
C. 33
D. 40
-
[简答题]
阅读下列程序,并回答问题: #include
请写出执行该程序后的输出结果;substr(char*t,char*s,int pos,int len) { while(len>0&&*s) { *t=*(s+pos-l); t++;s++;len--; } *t=’/0’; } char *f31(char*s) { char t[100]; if (strlen(s)=1) return s; substr(t,s,1,1); substr(s,s,2,strlen(s)-1); f31(s); return strcat(s,t); } main( ) { char str[100]= ’’String’’; printf(’’%s/n’’,f31(str)); }
-
[单项选择]若元素的入栈顺序为1,2,3....,n,如果第2个出栈的元素是n,则输出的第i(1<=i<=n)个元素是( )
A. n-i
B. n-i+l
C. n-i+2
D. 无法确定
-
[填空题]下面程序段的时间复杂度为___________。
sum=1;
for(i=0;sum
-
[单项选择]串匹配算法的本质是( )
A. 串复制
B. 串比较
C. 子串定位
D. 子串链接
-
[单项选择]如果在排序过程中不改变关键字相同元素的相对位置,则认为该排序方法是( )
A. 不稳定的
B. 稳定的
C. 基于交换的
D. 基于选择的
-
[填空题]使用一个100个元素的数组存储循环队列,如果采取少用一个元素空间的方法来区别循环队列的队空和队满,约定队头指针front等于队尾指针rear时表示队空。若为front=8,rear=7,则队列中的元素个数为___________。
-
[填空题]如果要为文件中的每个记录建立一个索引项,则这样建立的索引表称为___________。
-
[单项选择]若需高效地查询多关键字文件,可以采用的文件组织方式为( )
A. 顺序文件
B. 索引文件
C. 散列文件
D. 倒排文件
-
[单项选择]若一棵二叉树的前序遍历序列与后序遍历序列相同,则该二叉树可能的形状是( )
A. 树中没有度为2的结点
B. 树中只有一个根结点
C. 树中非叶结点均只有左子树
D. 树中非叶结点均只有右子树
-
[简答题]
要在[0..n-l]的向量空间中建立两个栈stackl和stack2,请回答:
应该如何设计这两个栈才能充分利用整个向量空间?
-
[单项选择]设有一组关键字(19, 14, 23, 1,6,20, 4,27, 5,11, 10, 9),用散列函数H(key)=key%13构造散列表,用拉链法解决冲突,散列地址为1的链中记录个数为( )
A. 1
B. 2
C. 3
D. 4
-
[简答题]
要在[0..n-l]的向量空间中建立两个栈stackl和stack2,请回答:
若stackl的栈顶指针为topl,stack2的栈顶指针为top2,如果需要充分利用整个向量空间,则:栈stackl空的条件是:___________;栈stack2空的条件是:___________;栈stackl和栈stack2满的条件是:___________。
-
[填空题]对任一m阶的B树,每个结点中最多包含___________个关键字。
-
[填空题]3个结点可以组成___________种不同树型的二叉树。
-
[填空题]用5个权值{3, 2,4,5,1}构造的哈夫曼(Huffman)树的带权路径长度是___________。
-
[单项选择]若带头结点的单链表的头指针为head,则判断链表是否为空的条件是( )
A. head=NULL
B. head->next=NULL
C. head!=NULL
D. head->next!=head
-
[简答题]已知线性表(a1,a2,a3...,an)按顺序存放在数组a中,每个元素均为整数,下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如,有7个整数的原始序列为(x,x,-x,-x,x,x,-x),变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容,使其成为完整的算法。f30(int a[],int n){ int k,m,temp;m= (1) ;while (a[m]<0 &&m
=0&&k -
[填空题]若两个关键字通过散列函数映射到同一个散列地址,这种现象称为___________。
-
[单项选择]若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点,要使操作时间最少,下列选项中,应选择的存储结构是( )
A. 无头结点的单向链表
B. 带头结点的单向链表
C. 带头结点的双循环链表
D. 带头结点的单循环链表
-
[填空题]若无向图G中有n个顶点m条边,采用邻接矩阵存储,则该矩阵中非0元素的个数为___________。
-
[填空题]影响排序效率的两个因素是关键字的___________次数和记录的移动次数。
-
[简答题]下面程序实现插入排序算法。typedef struct{ int key; Info otherinfo;}SeqList;void InsertSort(SeqList R[],int n){/* 待排序列保存在R[1..n]中*/ SeqList x; int i,j,k,lo,hi,mi; for (i=2;i<=n;i++) { (1) ; lo=1; hi=i-l; while (lo<=hi) { mi=(lo+hi)/2; if ( (2) ) break; if (R[mi].key>x.key) hi=mi-l; else lo=mi+l; } if (mi=lo) k=i - mi; else k=i - mi-1; for (j=0;j
(3) ; R[i-j]=x; }}在空白处填写适当的内容,使该程序功能完整。(1)(2)(3) -
[简答题]已知二叉树的定义如下:typedef struct node{ int data; struct node *lchild, *rchild;}*Bitptr;编写递归算法求二叉树的高度。函数原型为:int f34(Bitptr t);
-
[单项选择]数据的四种存储结构是( )
A. 顺序存储结构、链接存储结构、索引存储结构和散列存储结构
B. 线性存储结构、非线性存储结构、树型存储结构和图型存储结构
C. 集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构
D. 顺序存储结构、树型存储结构、图型存储结构和散列存储结构
-
[填空题]已知链表结点定义如下:
typedef struct node{
char data[16];
struct node *next;
} LinkStrNode;
如果每个字符占1个字节,指针占4个字节,则该链表的存储密度是___________。
-
[简答题]
设有单链表类型定义如下: typedef struct node { int data; struct node *next; } *LinkList; 阅读下列算法,并回答问题: void f33(LinkList head, int A, int B) { LinkList p=NULL; While (head !=NULL) { if (head->data>A&&head->datanext; } if (p !=NULL) printf("%d/n",p->data); }
简述算法f33的功能。
-
[简答题]
请回答下列问题:
英文缩写DAG的中文含义是什么?