数据结构2005软院补考题.docVIP

软件学院 2005级 补考题 2007.9.10 姓名 学号 1 2 3 4 5 6 7 8 得 分 1．算法分析题（10分, 每小题5分） 1）分析下列程序段中加下划线的语句执行次数 int x 91 ; int y 100 ; while y 0 if x 100 x - 10 ; y--; else x++; 答： 2）设有n个不同关键码的对象在排序前已按关键码由小到大排好序，用下列方法对其按关键码进行排序，需要进行比较的次数 : 直接插入排序: 。 快速排序: 。 冒泡排序: 。 2．（20分，每题10分） 1） 设有序顺序表中的元素依次为 017,094,154,170,275,503,509,512,553,612,677,765,897,908. 试画出对其进行折半有哪些信誉好的足球投注网站时的判定树, 并计算有哪些信誉好的足球投注网站成功的平均有哪些信誉好的足球投注网站长度。 答： 2 设数组Q[m]表示一个环形队列（下标为0 到m – 1）, rear为队列中最后一个元素的实际位置，length为队列中元素的个数, 求队列中第一个元素的实际位置（ 要求写出计算公式） 答： 3 10分 1 试述栈与队列的概念。 2）设有一字符串，次序为3*y─a/y↑2, 试利用栈将次序改为3y*ay2↑/─的操作步骤。（请用X代表扫描该字符串过程中顺序取一字符进栈的操作，用S代表从栈中取出一字符加入到新字符串尾的出栈操作。例如，要使ABC变为BCA，则操作步骤为XXSXSS） 答： 4．（10分） 对下列图 1 16 2 21 11 5 19 6 6 3 33 14 10 5 18 4 按照prim算法求从顶点 1 开始的最小代价生成树（要求画出构造过程的每一步）。 5.（10分） 设散列表HT[13]，散列函数为H key key % 13, 用开放定址法解决冲突，对关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 构造散列表，用线性探查法寻找下一个空位，画出散列表，并计算等概率下有哪些信誉好的足球投注网站成功的平均有哪些信誉好的足球投注网站长度ASLsucc。 答： 6. 10分 采用堆排序方法将初始序列 6, 15, 9, 5 按从小到大顺序排序, 则建立初始堆和排序过程中序列依次变化为 、 、 、 。 7.（10分 对下列关键码序列 1，26，3，23，4，24，25 ，依次插入一棵初始状态为空的AVL树中，画出每插入一个关键码后的AVL树。 答： 8. 10分 设有一个表头指针为first的单链表 不带表头结点 ，下面的算法通过一趟遍历将链表就地逆转（例如：a- b- c- d变为d- c- b- a），要求逆转后表头指针first指向原来链表中的最后一个结点。 data link first a b c ……. public void inverse ListNode f if f NULL return; ListNode p f . link ; pr NULL; while ; pr first ; first p ; p p . link ; ; 9．（10分） 给定一棵二叉树t，其根指针为root，结点结构为： left data right left, right分别指向该结点的左、右子树,假设data域为int型。试用java或C++语言写一个程序：给出该二叉树的类定义（仅写出必要的成员变量和成员函数），并写出判别该二叉树是否是二叉有哪些信誉好的足球投注网站树的算法。 答： 1