|
一单项选择题(本大题共小题每小题分共分) 在每小题列出的四个备选项中只有一个是符合题目要求的请将其代码填写在题后的括号内错选多选或未选均无分 若将数据结构形式定义为二元组(KR)其中K是数据元素的有限集合则R是K上( ) A 操作的有限集合 B 映象的有限集合 C 类型的有限集合 D 关系的有限集合 在长度为n的顺序表中删除第i个元素(≤i≤n)时元素移动的次数为( ) A ni+ B i C i+ D ni 若不带头结点的单链表的头指针为head则该链表为空的判定条件是( ) A head==NULL B head>next==NULL C head!=NULL D head>next==head 引起循环队列队头位置发生变化的操作是( ) A 出队 B 入队 C 取队头元素 D 取队尾元素 若进栈序列为且进栈和出栈可以穿插进行则不可能出现的出栈序列是( ) A B C D 字符串通常采用的两种存储方式是( ) A 散列存储和索引存储 B 索引存储和链式存储 C 顺序存储和链式存储 D 散列存储和顺序存储 设主串长为n模式串长为m(m≤n)则在匹配失败情况下朴素匹配算法进行的无效位移次数为( ) A m B nm C nm+ D n 二维数组A[][]采用列优先的存储方法若每个元素各占个存储单元且第个元素的地址为则元素A[][]的地址为( ) A B C D 对广义表L=((ab)(cd)(ef))执行操作tail(tail(L))的结果是( ) A (ef) B ((ef)) C (f) D ( ) 下列图示的顺序存储结构表示的二叉树是( ) n个顶点的强连通图中至少含有( ) A n条有向边 B n条有向边 C n(n)/条有向边D n(n)条有向边 对关键字序列()进行增量为的一趟希尔排序的结果为( ) A () B ) C () D () 若在阶B树中插入关键字引起结点分裂则该结点在插入前含有的关键字个数为( ) A B C D 由同一关键字集合构造的各棵二叉排序树( ) A 其形态不一定相同但平均查找长度相同 B 其形态不一定相同平均查找长度也不一定相同 C 其形态均相同但平均查找长度不一定相同 D 其形态均相同平均查找长度也都相同 ISAM文件和VSAM文件的区别之一是( ) A 前者是索引顺序文件后者是索引非顺序文件 B 前者只能进行顺序存取后者只能进行随机存取 C 前者建立静态索引结构后者建立动态索引结构 D 前者的存储介质是磁盘后者的存储介质不是磁盘 二填空题(本大题共小题每空分共分) 数据的逻辑结构在计算机存储器内的表示称为数据的____________ 删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________ 栈下溢是指在____________时进行出栈操作 已知substr(silen)函数的功能是返回串s中第i个字符开始长度为len的子串strlen(s)函数的功能是返回串s的长度若s=″ABCDEFGHIJK″t=″ABCD″执行运算substr(sstrlen(t) strlen(t))后的返回值为____________ 去除广义表LS=(aaa……an)中第个元素由其余元素构成的广义表称为LS的____________ 已知完全二叉树T的第层只有个结点则该树共有____________个叶子结点 在有向图中以顶点v为终点的边的数目称为v的____________ 当关键字的取值范围是实数集合时无法进行箱排序和____________排序 产生沖突现象的两个关键字称为该散列函数的____________ 假设散列文件中一个桶能存放m个记录则桶溢出的含义是当需要插入新的记录时该桶中____________ 三解答题(本大题共小题每小题分共分) 假设以数组seqn[m]存放循环队列的元素设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数 ()写出队满的条件表达式; ()写出队空的条件表达式; ()设m=rear=quelen=求队头元素的位置; ()写出一般情况下队头元素位置的表达式 () () () () 已知一棵二叉树的中序序列为ABCDEFG层序序列为BAFEGCD请画出该二叉树 画出下图所示有向图的所有强连通分量 对个关键字进行快速排序在最好的情况下仅需进行次关键字的比较 ()假设关键字集合为{}试举出能达到上述结果的初始关键字序列; ()对所举序列进行快速排序写出排序过程 () () 四算法阅读题(本大题共小题每小题分共分) 阅读下列算法并回答问题 ()设顺序表L=()写出执行f(&L)之后的L; ()设顺序表L=()写出执行f(&L)之后的L; ()简述算法的功能 void f(SeqList*L DataType x) { int i = j; while (ilength && x>L>data[i])i++; if(ilength && x==L>data[i]) { for(j=i+;jlength;j++) L>data[j]=L>data[j]; L>length; } else { for(j=L>length;j>i;j) L>data[j]=L>data[j]; L>data[i]=x; L>length++; } } () () () 已知图的邻接表表示的形式说明如下 #define MaxNum //图的最大顶点数 typedef struct node { int adjvex; //邻接点域 struct node *next; //链指针域 } EdgeNode; //边表结点结构描述 typedef struct { char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 } VertexNode; //顶点表结点结构描述 typedef struct { VertexNode adjlist[MaxNum]; //邻接表 int n e; //图中当前的顶点数和边数 } ALGraph; //邻接表结构描述 下列算法输出图G的深度优先生成树(或森林)的边阅读算法并在空缺处填入合适的内容使其成为一个完整的算法 typedef enum {FALSE TRUE} Boolean; Boolean visited[MaxNum]; void DFSForest(ALGraph *G){ int i; for(i=;in;i++) visited[i]=___________________(); for(i=;in;i++) if (!visited[i]) DFSTree(Gi); } void DFSTree(ALGraph *G int i) { EdgeNode *p; visited[i]=TRUE; p=G>adjlist[i] firstedge; while(p!=NULL){ if(!visited[p>adjvex]){ printf(″ |
