|
中山大学2007年考研数据结构试题五、设计题（编程语言不限）（共44分）1.设有一个整数数组B{0….N},请设计一个算法，求出B中相邻两个元素之和刚好是100的组合的个数。（6分）2.设有一个单向循环链表结构，first是指向头结点的指针。（1）请编写一个算法，将此链表中数据最小的节点从链表中删除。（10分）（2）请分析你的算法的时间复杂度。（3分）3.单孩子结点指的是那些只有左孩子而没有右孩子的结点，或者只有右孩子而没有左孩子的结点。（1）请给出计算一棵二叉树的单孩子节点数的递归模型。（5分）（2）假定这棵二叉树采用链式存储结构，请设计一个算法，计算给定这棵二叉树的单孩子结点数。（10分）4．编写一个算法，借助于两个临时栈stack1 和stack2，利用栈的基本运算将指定栈mystack中的内容逆转。答案：int count(int B[],int N){ int k=0; for(int i=0;inext; int min=p->data; while(p->next!=first) { if(p->next->datanext->data;q=p; } p=p->next; } p=q->next; q->next=p->next; free(p);}如果表中有n的元素，时间复杂度为O(n)3.这是左右孩子链式结构的算法int count(bitree root){ if(!root)return 0;else { if(root->lchild&&!root->rchild)return 1+count(root->lchild); else if(!root->lchild&&root->rchild)return 1+count(root->rchild); else return count(root->lchild)+count(root->rchild); }}4.void fun(stack &mystack){ while(!StackEmpty(mystack)) { Pop(mystack,e); Push(stack1,e); } while(!StackEmpty(stack1)) { Pop(stack1,e); Push(stack2,e); } while(!StackEmpty(stack2)) { Pop(stack2,e); Push(mystack,e); }}兄弟抱歉！学校的真题一般是很难泄露的！我找半天才找到一道似乎是的，希望对你有点启发吧。 |
