《数据结构》题型和答案.pdf

数据结构试卷数据结构试卷 A 第第 1 页页 共共 5 页页 一一. 单单项选择项选择题题 1. 若若 str1 存储为字符序列存储为字符序列 SCUT$; 执行下列语句后执行下列语句后 str2 存储存储的的字符序列字符序列是是_。 PUSH(STACK, $); i=0; while ( *(str1+i)!=$ ) PUSH(STACK, *(str1+i); i+; i=0; *(str2+i)= POP(STACK); while (*(str2+i)!= $ ) i+; *(str2+i)=POP(STACK); *(str2+i)=POP(STACK); (A) SCUT; (B) TUCS$; (C) TC$; (D) TC. 2. int fun(struct node *f, struct node *r) 实现的功能实现的功能是是_。 struct node int data; struct node *link; ; int fun(struct node *f, struct node *r) struct node *q; int item; if(*f=NULL) printf(“empty”); else if(*f=*r) item=(*f)-data; free(*f); *f=NULL; *r=NULL; else q=*f; item=q-data; *f=(*f)-link; (*r)-link=*f; free(q); return item; return NULL; (A) 普通队列中普通队列中插入结点；插入结点； (B) 普通队列普通队列中中删除删除结点；结点； (C) 环形队列中环形队列中删除删除结点结点； (D) 环形队列中环形队列中插入插入结点结点. 3.设单设单向向链表中结点的结构为链表中结点的结构为 struct node int data; int link; ; struct node *p, *s, *q. 已知已知 指针指针 p-link =s; s-link=q; 若在若在*p 与与*q 之间之间删除删除结点结点*s，则应执行操作，则应执行操作_。 (A) q-link=q; (B) q-link=p; (C)p-link=q; (D) p-link=p. 4. 由由二叉树二叉树的根开始，的根开始，令令 a=3, 8, 7, 9, 1, 2, 4，依次调用函数依次调用函数*create，执行执行下列语句下列语句后后建立建立 的的二叉二叉树树是是 Fig.1 中的中的_。 struct tree *create(struct tree *root, int a) if (root=NULL) root=(struct tree *)malloc(sizeof(struct tree); root-data=a; root-left=NULL; root-right=NULL; return(root); else if(adata) root-left=create(root-left, a); else root-right=create(root-right, a); (A) (C) (D) (B) 数据结构试卷数据结构试卷 A 第第 2 页页 共共 5 页页 return(root); 其中其中: struct tree int data; struct tree *left; struct tree *right; ; 二二. 填空填空题题 1.The POSTfix expression: ABCD-+EAC/-*，write down the corresponding INfix and PREfix expressions: _ 2. Consider the following variable-length codes for the 36-character text string: F C F C E C A C B D E D F E A B F B A F F C D C B E D F F F C C D E E F Using the Huffman encoding, fill in the Table 1. 3. Please show the different traversal output on the following tree: PRE-order Depth-First Traversal (DFT) _ IN-order Depth-First Traversal (DFT) _ POST-order Depth-First Traversal (DFT)_ Breadth First Search Traversal (BFST)_ 三三. 算法算法分析分析题题 1. Implementation of binary tree and its breadth first and depth first traversal operation. 以以 Fig.3 tree为例为例，分别详细分析分别详细分析： (1.1) breadth(tree *rt)执行过程中执行过程中queue的变化过程的变化过程和输出结果和输出结果； (1.2) depth(tree *rt) 执行过程中执行过程中stack的变化过程的变化过程和输出结果和输出结果； 用具体图表示每一个入队列、出队列和进栈、出栈过程。用具体图表示每一个入队列、出队列和进栈、出栈过程。 假设假设tree node为：为： typedef struct node char data; struct node *lp,*rp; tree; Symbols A B C D E F Fixed Length Codes Occur Frequency Huffman Codes Fig. 1 Fig. 2 Table 1 Fig. 3 数据结构试卷数据结构试卷 A 第第 3 页页 共共 5 页页 2. Graph Manipulations: Use the following graph for this problem. Assume that any algorithm begins at node A. (2.1) Draw both the adjacency matrix and adjacency list representations of this graph. Be sure to specify which is which. (2.2) Starting from A, write down the results of BFS and DFS traversal. Write down the detail contents of the queue or stack in the traversal. (2.3) Give two valid topological orderings of the nodes in the graph. (2.4) Through Dijkstras Algorithm, calculate the Single source Shortest path from A to every other vertex. void breadth(tree *rt) queue *q; tree *u,*son; q=NULL; son=NULL; enqueue( while(q!=NULL) u=dequeue( printf(“%d “,u-data); if (u-lp)!=NULL) son=u-lp; enqueue( if (u-rp)!=NULL) son=u-rp; enqueue( void depth(tree *rt) /*pre-order*/ stack *top; tree *son; top=NULL; son=rt; while (son!=NULL)|(top!=NULL) while (son!=NULL) printf(“%d “,son-data); push( son=son-lp; if (top!=NULL) son=pop( son=son-rp; Fig. 4 数据结构试卷数据结构试卷 A 第第 4 页页 共共 5 页页 四四. 算法设计题算法设计题 1. The following pseudocode is an implementation of Binary Nodes for integers. class BinaryNode int element; / The data in the node BinaryNode left; / Left child BinaryNode right; / Right child BinaryNode ( int theElement, BinaryNode L, BinaryNode R ) element=theElement; left=L; right=R; Add a method BinaryNode findMin( ) that returns the binary node with LEAST value in this binary node (the tree that this node is root for). Do not assume the tree has the search property (any integer value can be anywhere in the tree). Hint: you may apply recursive or non-recursive method. 2. Figure 5 illustrates a specific family of networking topologies. This network has a mix of full duplex (communication can reverse both directions) and simplex connections communication can reverse ONLY one direction). Assume a network of this type is in existence, where each ring(there are r rings in total) has all n number of nodes. The unique central node has IP number 100.100.0.0. The central node has full duplex connections to one node in each ring (100:100:i:1 is the node in the ith ring connected to the central node). In each ring, there is one simplex connection from every node to the next one in the ring, such that for the ith ring, the jth node has IP (100:100:i:j) and is simplex connected to (100:100:i:j+1), with the exception of the last node in the ring, which is connected simplex back to (100:100:i:1). Figure 5 illustrates an example. When a topology is structured like this finding a closest path through the graph is much simplified, and does not require anything but simple consideration of the topology. For example, for the case of figure 5, if one wants to go from node (100:100:2:4) to node (100:100:1:2), the path would look like: Fig. 5 An example of the network topology with r=3, n=4. There are 12 simplex connections and 3 duplex connections (A, B, C). A B C 数据结构试卷数据结构试卷 A 第第 5 页页 共共 5 页页 100.100.2.4 100.100.2.1 100.100.0.0 100.100.1.1 100.100.1.2 (2.1) Given r rings with n nodes, give an expression for the longest possible path (expressed either in number of links traversed OR nodes visited). (2.2) Make a method called: printPath(int r, int n, int sr, int sn, int dr, int dn), that prints the path from a node with IP(100.100.sr.sn) to a node with IP(100.100.dr.dn) in a with r rings with n nodes. Hint: you may apply recursive or non-recursive method. 数据结构试卷数据结构试卷 A 答案答案 第第 1 页页 共共 5 页页 一一. 单单项选择项选择题题 题号题号 1 2 3 4 答案答案 C C C D 二二. 填空填空题题 1. INfix: (A+(BC-D)*(E-(A/C) PREfix: *+A-BCD-E/AC 2. 3. PRE-order Depth-First Traversal (DFT): +*AB/CD IN-order Depth-First Traversal (DFT): A*B+C/D POST-order Depth-First Traversal (DFT): AB*CD/+ Breadth First Search Traversal (BFST): +*/ABCD 三三. 算法算法分析分析题题 1. (1.1) (1.2) Symbols A B C D E F Fixed Length Codes 000 001 010 011 100 101 Occur Frequency 3 4 8 5 6 10 Huffman Codes 11111 11110 10 1110 110 0 数据结构试卷数据结构试卷 A 答案答案 第第 2 页页 共共 5 页页 2. (2.1) (2.2) DFST: In Stack: Top to Bottom 1: A 2: E D B 3: C D B 4: D D B 5: D B 6: B A E C D B BFST: In Queue: Front to Rear 1: A 2: B D E 3: D E D 4: E D 5: D C 数据结构试卷数据结构试卷 A 答案答案 第第 3 页页 共共 5 页页 6: C A B D E C (2.3) (a) A B E C D (b) A E B C D (2.4) AB=5; AC=-1; AD=10; AE=6; B: ABC=-1; ABD=8; ABE=-1 AC=BC=-1; AD=ABD=8; AE=6 E: AEC=10; AED=-1 AC=AEC=10; AD=ABD=8; D: ADC=-1 AEC=10 AB=5; AEC=10; ABD=8; AE=6 四四. 算法设计题算法设计题 1. BinaryNode findMin( ) minVal = element; if(left != null) minVal = min(minVal, left.findMin(); if(right != null) minVal = min(minVal, right.findMin(); return minVal; 2. (2.1) Note that we implicitly assume that r 1 and n1. We have. Number of NODEs in longest path: 2n + 1. Number of LINKs in longest path: 2n. A special case may be noticed for when r = 1. If only one ring is present(r=1), then the longest path becomes n links (still assuming an extra node with duplex connection). (2.2) There are many ways of doing this. We will assume there is a help function incrementInRing: 数据结构试卷数据结构试卷 A 答案答案 第第 4 页页 共共 5 页页 int incrementInRing(int node, int nofNodes) node+; if (node nofNodes) node = 1; return node; Pseudo code solution: printPath(int r, int n, int sr, int sn, int dr, int dn) /on each jump or node increment, println the