清华大学2001年考研真题-数据结构

本站小编 FreeKaoyan/2018-01-22

清华大学2001年“数据结构”试题

试题内容:
一、试给出下列有关并查集(mfsets)的操作序列的运算结果:
union(1,2) , union(3,4) , union(3,5) , union(1,7) , union(3,6) , union(8,9) , union(1,8) , union(3,10) , union(3,11) , union(3,12) , union(3,13) , union(14,15) , union(16,0) , union(14,16) , union(1,3) , union(1,14)。(union是合并运算,在以前的书中命名为merge)
要求
(1) 对于union(i,j),以i作为j的双亲; (5分)
(2) 按i和j为根的树的高度实现union(i,j),高度大者为高度小者的双亲; (5分)
(3) 按i和j为根的树的结点个数实现union(i,j),结点个数大者为结点个数小者的双亲; (5分)
二、设在4地(A,B,C,D)之间架设有6座桥,如图所示:

要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地
(1) 试就以上图形说明:此问题有解的条件是什么? (5分)
(2) 设图中的顶点数为n,试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法,找出满足要求的一条回路. (10分)
三、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数):
(1) 输入的n个数据全部有序; (5分)
(2) 输入的n个数据全部逆向有序; (5分)
(3) 随机地输入n个数据. (5分)
四、简单回答有关AVL树的问题.
(1) 在有N个结点的AVL树中,为结点增加一个存放结点高度的数据成员,那么每一个结点需要增加多少个字位(bit)? (5分)
(2) 若每一个结点中的高度计数器有8bit,那么这样的AVL树可以有多少层?最少有多少个关键码? (5分)
五、设一个散列表包含hashSize=13个表项,.其下标从0到12,采用线性探查法解决冲突. 请按以下要求,将下列关键码散列到表中.
10 100 32 45 58 126 3 29 200 400 0
(1) 散列函数采用除留余数法,用%hashSize(取余运算)将各关键码映像到表中. 请指出每一个产生冲突的关键码可能产生多少次冲突. (7分)
(2) 散列函数采用先将关键码各位数字折叠相加, 再用%hashSize将相加的结果映像到表中的办法. 请指出每一个产生冲突的关键码可能产生多少次冲突. (8分)
六、设一棵二叉树的结点定义为
struct BinTreeNode{
ElemType data;
BinTreeNode *leftChild, *rightChild;
}
现采用输入广义表表示建立二叉树. 具体规定如下:
(1) 树的根结点作为由子树构成的表的表名放在表的最前面;
(2) 每个结点的左子树和右子树用逗号隔开. 若仅有右子树没有左子树, 逗号不能省略.
(3) 在整个广义表表示输入的结尾加上一个特殊的符号(例如”#”)表示输入结果.
例如,对于如右图所示的二叉树, 其广义表表示为A(B(D,E(G,)),C(,F))
A
/
B C
/
D E F
/
G
此算法的基本思路是:依次从保存广义表的字符串ls中输入每个字符. 若遇到的是字母(假定以字母作为结点的值), 则表示是结点的值, 应为它建立一个新的结点, 并把该结点作为左子女(当k=1)或有子女(当k=2)链接到其双亲结点上. 若遇到的是左括号”(“, 则表明子表的开始,将k置为1;若遇到的是右括号”)”, 则表明子表结果. 若遇到的是逗号”,”, 则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子树, 将k置为2.
在算法中使用了一个栈s, 在进入子表之前,将根结点指针进栈, 以便括号内的子女链接之用. 在子表处理结束时退栈. 相关的栈操作如下:
MakeEmpty(s) 置空栈
Push(s,p) 元素p进栈
Pop(s) 进栈
Top(s) 存取栈顶元素的函数
下面给出了建立二叉树的算法, 其中有5个语句缺失. 请阅读此算法并把缺失的语句补上. (每空3分)
Void CreateBinTree(BinTreeNode *&BT, char ls){
Stacks; MakeEmpty(s);
BT=NULL; //置二叉树
BinTreeNode *p;
int k;
istream ins(ls); //把串ls定义为输入字符串流对象ins
Char ch;
ins>>ch; //从ins顺序读入一个字符
While(ch!=”#”){ //逐个字符处理,直到遇到'#'为止
Switch(ch){
case’(‘: _______(1)_______
k=1;
break;
case’)’: pop(s);
break;
case’,‘: _______(2)_______
break;
default: p=new BinTreeNode;
_______(3)_______
p->leftChild=NULL;
p->rightChild=NULL;
if(BT==NULL)
_______(4)_______
else if (k==1) top(s)->leftChild=p;
else top(s)->rightChild=p;
}
_______(5)_______
}
}
七、下面是一个用C编写的快速排序算法. 为了避免最坏情况,取基准记录pivot采用从left,right和mid=[(left+right)/2]中取中间值, 并交换到right位置的办法. 数组a存放待排序的一组记录, 数据类型为Type, left和right是呆排序子区间的最左端点和最右端点.
Void quicksort(Type a&#;,int left,int right){
Type temp;
If(leftType pivot=median3(a,left,right);
Int I=left, j=right-1;
For( ; ; ){
While(iWhile(iif(itemp=a[i]; a[j]=a[i]; a[i]=temp;
I++; j--;
}
else break;
}
if(a[i]>pivot)
{temp=a[i]: a[i]=a[right]; a[right]=temp;}
quicksort(a,left,i-1); //递归排序左子区间
quicksort(a,i+1,right); //递归排序右子区间
}
}
(1) 用C或Pascal实现三者取中子程序 median3(a,left,right); (5分)
(2) 改写 quicksort 算法, 不用栈消去第二个递归调用 quicksort(a,i+1,right); (5分)
(3) 继续改写 quicksort 算法, 用栈消去剩下的递归调用. (5分)



相关话题/清华大学 考研真题 数据结构

  • 领限时大额优惠券,享本站正版考研考试资料!
    大额优惠券
    优惠券领取后72小时内有效,10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材,产品类型包含电子书、题库、全套资料以及视频,无论您是考研复习、考证刷题,还是考前冲刺等,不同类型的产品可满足您学习上的不同需求。 ...
    本站小编 Free壹佰分学习网 2022-09-19
  • 清华大学2001年考研真题-计算机原理
    清华大学2001年硕士入学计算机原理试题一、(10分)某RISC处理机各类指令使用频率和理想CPI(指令和数据访问Cache命中率为100%时的CPI)如下表所示。而实际测得的指令访问Cache缺失率(miss rate)为5%,数据访问的Cache缺失率为10%,Cache的缺失损失(miss p ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2001年考研真题-新闻理论考研试题及参考答案
    清华大学2001年新闻理论考研试题及参考答案一、解释下列概念(每题4分,共20分)1. 原始新闻【参考答案】原始新闻泛指原始社会的口头新闻、声光新闻和图画新闻,新闻传播手段的原始性使其停留在对自然物的选择上。氏族间运用自然物互告消息,是原始新闻的第一个特征;在任何一个原始人的头脑中,还没有出现通过新 ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2001年考研真题-编译原理和操作系统
    清华大学2001年“编译原理和操作系统”试题编译原理部分1.(5%) 给出下述NFA M的五元组表示, 并将其确定化 2 (5%) 构造一个不具有ε-转移的NFA M’ , 使得L(M’)=L(M) 3 (10%) 证明文法G[A]是LR(1)文法.G[A]:A->BA|εB->aB|b4 (5%) ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2001年考研真题-编译原理及操作系统
    清华大学2001年硕士入学编译原理及操作系统试题编译原理部分1.(5%) 给出下述NFA M的五元组表示, 并将其确定化2 (5%) 构造一个不具有ε-转移的NFA M’ , 使得L(M’)=L(M)3 (10%) 证明文法G[A]是LR(1)文法. G[A]: A->BA|ε B->aB|b4 ( ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2001年考研真题-古代汉语
    2001年—语言学及应用语言学—古代汉语一、名词解释。每题2分,共10分。1、简牍 2、汗青 3、帙4、付梓 5、句读6、衍文7、文、字8、《马氏文通》9、押韵10、破读二、请简答并举例(每题4分,共20分。)1、连绵字2、三十六字母3、反切4、今体诗及其特点5、十三经注疏三、填空。每空0.5分,共 ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2000年考研真题-古代汉语
    2000年——语言学及应用语言学——古代汉语一、标点并翻译。 15分 1、下臣不幸属当戎行无所逃匿且擢奔辟而忝两君臣辱戎士敢告不敏摄官承乏 2、是故无冥冥之志者无昭昭之明无昏昏之事者无赫赫之功 3、臣闻始时吕尚之遇文王也身为渔父而钓于渭阳之滨而若是者交疏也已一说而立为太师载与俱归者其言深也故文王果收 ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2000年考研真题-现代汉语
    2000年——语言学与应用语言学——现代汉语一、简述现代汉语和近代汉语的关系。5分二、谈谈元音和辅音的特点。4分三、指出普通话中下列各对音素的异同。4分 (1)、b[p] p[p‘] (2)、z[ts] zh[t,s] (3)、i u(4)、e[e] o[o]四、普通话中的单元音都是舌面元音吗?为什 ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2000年考研真题-语言学概论
    2000年——语言学及应用语言学——语言学概论一、填空。34分1、语言是(   )。1分2、运用语言进行交际的过程,如果借用信息论的术语来说,大体上可以分为(  )——发送——(  )——接收——(  )五个阶段。1.5分3、如果一个病人大脑()半球发生损伤,他尽管说不出他家的住址,却认得自己的家门 ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2006年考研真题-计算机原理
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学1996年考研真题-中国思想史中国通史
    考试科目:中国通史 专业:中国思想史 一、解释名词 1、先秦百家争鸣 2、三省六部制 3、绍兴和议 4、郑和下西洋 二、试述自秦到明清地方行政机构的变化 三、分析洋务运动的起因、性质及作用 试科目:中国思想史 专业:考专门史 一、解释名词(各5分) 1、后期墨家 2、浙东学派 3、全真道 4、华 ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学1996年考研真题-专门史中国通史
    考试科目:中国通史 专业:专门史 一、解释名词(各5分) 1、殷墟 2、吴起变法 3、牛李党争 4、天工开物 二、写出廿四史的作者、名称、成书时代(25分) 三、试述王安石变法的背景及内容(20分) 四、试论鸦片战争对中国社会的影响(30分) 考试科目:中国古代史 专业:专门史 一、试述王莽改制的 ...
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2003年考研真题-信号系统与电子电路
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2005年考研真题-物理化学
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2001年考研真题-有机化学
    本站小编 FreeKaoyan 2018-01-22
  • 清华大学2002年考研真题-计算机考研试题
    本站小编 FreeKaoyan 2018-01-22