您的位置:考研教育网> >历年试题>考研专业课> 正文

同济大学2002年数据结构与程序设计考研试题

考研教育网   2009-10-30 10:17 【 】【我要纠错

  业务码                    业务名称   数据结构与程序设计(C)             (013)

  适用专业:检测技术与自动化装置   成人教育学  电机与电器   电力系统及其自动化

  信与信息系统  控制理论与控制工程  系统工程     模式识别与智能系统|

  计算机系统结构  管理科学与工程     0816         结构工程|

  交通信息工程及控制  交通运输规划与管理   计算机软件理论  计算机应用技术

  数据结构部分:

  1.[10分]设有一个工程包含了8个子工程,这些子工程之间有如下的优先关系:

  1>2,3,4           3>5           5>7,  8 2>3, 6            4>7           6>5,  8

  (这里,1>2,3,4表示子工程1需要在子工程2,3,4开始前完成,其它的依次类推)

  如果在邻接表存储结构中,每个顶点的邻接点序号是从小到大链接时,试写出其拓扑有序序列,并说明这个工程的可行性。

  2.[10分]已知待散列存储的关键字序列为(4,15,38,49,33,60,27,71),哈希函数为H(key)=key MOD 11,哈希表HT的长度为11.采用二次探测再散列法解决冲突,试构造此哈希表,并写出在等概率情况下的平均查找长度。

  3.[10分]二叉树的二叉链表表示为:

  类C语言                                    类PASCAL语言

  typedef struct bnode{                     TYPE  bitreptr=↑bnodetp;

  char data;                                 bnodetp=RECORD

  struct bnode *Lchild,*Rchild;                           data:char;

  }BNODE;                                                Lchild,Rchild:bitreptr

  END;

  以下是分别用类C语言和类PASCAL语言描述的二叉树后序遍历的非递归算法,其中,使用一个顺序栈stack,栈顶指针为top;s为标志数组;p为辅助指针。

  类C语言                                  类PASCAL语言

  void  postorder(BNODE *p)                 PROC postorder(p:bitreptr);

  {top=0;                                    top:=0;

  do{                                        REPEAT

  while(p!=NULL) {                          WHILE p<>NIL DO

  top++;                                   [ top:=top+1;

  stack[top]=p;                               stack[top]:=p;

  s[top]=0;                                  s[top]:=0;

  (1)______;                                (1)______;]

  }                                        WHILE(s[top]=1)AND(top>0) DO

  while((s[top]= =1)&&(top>0)){                 [ (2)________;

  (2)________;                                 (3) ________;

  (3) ________;                                write(p↑。data)]

  printf(“%c”,p→data);                       IF top>0

  }                                            THEN [s[top]:=1;

  if(top>0){                                           (4)_________;}

  s[top]=1;                             UNTIL top=0

  (4)________;                       ENDP;

  }

  }while(top!=0)

  }

  4.[10分]试写出在含有n个元素的堆中增加一个新元素x,且调整为堆的算法。

  说明: (1)本题中的堆为小顶堆。

  (2)每个元素为一个记录,类型rectype,其中,关键字域为key;由n个记录

  R[1]到R[n]所组成的文件类型为filetype.

  5.[10分]在某商店仓库中,欲对电视机按其价格从低到高的次序构造一个头指针为head的、

  不带表头结点的单循环链表,链表的每个结点指出同样价格的电视机的台数。现有m台价格

  为n元的电视机入库,试编写出仓库电视机的进货算法。

  链表的结点类型表示:

  类C语言                                       类PASCAL语言

  typedef struct list{                                TYPE linkisttp=↑nodetp;

  float price;(价格)                           nodetp=RECORD

  int   num;(数量)                                    price:real; (价格)

  struct  list *next;                                    num:integer;(数量)

  }Linklist;                                           next:linkisttp

  END;

  说明:请在4,5题的答案中,先说明算法思想或步骤,然后任选C语言或类PASCAL语言写出算法。

  请点击查看更多同济大学考研相关信息>>

  相关链接:同济大学历年考研专业课试题汇总

◇ 编辑推荐
·2015年考研复习:政治 英语 数学  专业课 · 2014年考研真题及答案汇总   历年考研真题
· 考研网上辅导热招!  ·2015年考研报考指南   ·历年考研国家分数线汇总   复试信息
考研网上辅导课程 特色班 精品班 实验班
学费 购买 学费 购买 学费 购买
公共课 政 治 800元 购买 1500元 购买 3500元 购买
英 语 800元 购买 1500元 购买 3500元 购买
数 学 800元 购买 1500元 购买 3500元 购买

专业课

视频

《管理类联考综合》、《会计学》、《中医综合》、《西医综合》、《法硕联考综合(法学)》、
《法硕联考综合(法学)》、《法硕联考专业基础(法学)》、《法硕联考专业基础(非法学)》

专业课

资料

952所考研院校、57300个招生专业、245000份考研辅导课件、核心纲要、考研笔记、内部题库现正热卖!

说明 专业课请到考研开放平台上注册及缴费----帮助