上饶师范学院模拟试题二.doc

PAGE 第 PAGE 3 页 上 饶 师 范 学 院 模 拟 试 题 二 课程名称： 数据结构 适用学期：第 四 学期 适用专业： 计算机科学与技术 适用层次： 本 科 班级： 学号： 姓名 题号 一 二 三 四 五 六 七 总分 得分 阅卷教师签名 得分 选择题：(每小题2分，10小题共20分) 数据结构是一门研究计算机中( )对象及其关系的学科。 A. 数值运算 B. 非数值运算 C. 集合 D. 非集合 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。 A. s-link=p;p-next=s; B. s-link=p-link;p-link=s; C. s-link=p-link;p=s; D. p-link=s;s-link=p; 在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。A. front=maxSize B. (rear+1)%maxSize=frontC. rear=maxSize D. rear=front 设有串t=“I am a good student”，那么subStr(t,6,6)=( )。 A. “student” B. “a good s” C. “good” D. “a good” 一个二叉树按顺序方式存储在一个维数组中，如图 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点G在二叉树的第（ ）层, 规定根结点为第0层。 A. 1 B. 2 C. 3 D 在一棵具有4层的满二叉树中结点总数为 ( )。 A. 31 B. 32 C. 33 利用逐点插入法建立序列{50,72,43,85,20,35,45,65,30}对应二叉排序树以后，查找元素35要进行( )元素间的比较。 A．4次　B. 5次　C. 7次　D. 10次 一有向图的邻接表存储结构如图所示，按深度优先算法，从v1出发得到的顶点序列为( ) A. v1,v3,v2,v4,v5 B. v1,v3,v4,v2,v5 C. v1,v2,v3,v4,v5 D. v1,v3,v4,v5,v2 在下列算法中，( )算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 插入排序 D. 快速排序 对于关键字序列{46，58，15，45，90，18，10，62}，其快速排序第一趟的结果是( )。 A. 15 45 18 46 10 62 58 90 B. 10 15 18 45 46 58 62 90 C. 10 18 15 45 46 90 58 62 D. 15 10 18 45 46 62 58 90 得分 填空题：(每小题2分，分值平均分配在每小空上，8小题共16分) 下面程序段的时间复杂度是__ ___。for(i=0;in;i++) for(j=0;jm;j++)A[i][j]=0; 在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。 设有串t=“I?am a?student”，s=“ good!”，那么concat(t,s)= ，subStr(t,8,7)= . 栈、队列逻辑上都是_________________结构 具有n个叶子的二叉树，每个叶子的权值为wi(1≤i≤n)其中带权路径最小的二叉树被称为?　　　　　　　?。 设有100个数据元素，采用折半搜索时，最大比较次数为___ ______。 若已知一棵二叉树的先序序列为 – + a * b – c d / e f，中序序列为a + b * c – d – e / f，则其后序序列为___________________。 在所学的排序算法中，第一趟排序完毕后，其最大或最小元